[백준] 13460-구슬 탈출2(C++)

문제링크:https://www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

 

 

이 문제는 13459번 구슬 탈출과 동일한 문제입니다. 다만 이동 경로값을 출력해주어야 하기 때문에 기존에 bfs를 사용하는게 편하다는 점이 있습니다. 

 

 

1. bfs와 while문을 사용하여 행동을 구현한다.

    - 이동할 곳이 #이 아니고 현재있는 좌표가 O가 아니면 계속 이동하게끔 구현한다.

2.이동후 두좌표가 같을때를 확인해준다.

    - 경우는 2가지이다. 함께 O에 있을때, 한쪽 끝에 함께 몰려있을때  함께 O라면 실패이기 때문에 큐에 넣지않고 마무       리 한쪽 끝이라면 값을 비교해서 하나를 한칸뒤로 무른다. 

3. 매 반복마다 result값을 증가시킨다. (구슬 탈출2 에서 유효)

 

 

정답코드입니다.

 

#include <iostream>
#include <queue>
#include <math.h>
using namespace std;

int n = 0, m = 0;
char arr[11][11];
bool visited[11][11][11][11] = { 0, };
int result = 0;

int ry, rx, by, bx;
int y_ar[4] = { 0,0,1,-1 };
int x_ar[4] = { 1,-1,0,0 };


int bfs() {
	queue <pair<int, int>> red_que;
	queue <pair<int, int>> blue_que;
	red_que.push(make_pair(ry, rx));
	blue_que.push(make_pair(by, bx));
	visited[ry][rx][by][bx] = 1;
	

	while (!red_que.empty()) {
		int sized = red_que.size();



		while (sized--) {

			int red_cy = red_que.front().first;
			int red_cx = red_que.front().second;
			int blue_cy = blue_que.front().first;
			int blue_cx = blue_que.front().second;


			red_que.pop(), blue_que.pop();

			if (arr[red_cy][red_cx] == 'O')
				return result;

			for (int i = 0; i < 4; i++) {
				int red_ny = red_cy;
				int red_nx = red_cx;
				int blue_ny = blue_cy;
				int blue_nx = blue_cx;

				while (arr[red_ny + y_ar[i]][red_nx + x_ar[i]] != '#' && arr[red_ny][red_nx] != 'O') {
					red_ny += y_ar[i];
					red_nx += x_ar[i];

				}
				while (arr[blue_ny + y_ar[i]][blue_nx + x_ar[i]] != '#' && arr[blue_ny][blue_nx] != 'O') {
					blue_ny += y_ar[i];
					blue_nx += x_ar[i];
				}

				if (red_ny == blue_ny && red_nx == blue_nx) {

					if (arr[red_ny][red_nx] == 'O') continue; // 할 필요가 없지

					if ((abs(red_ny - red_cy) + abs(red_nx - red_cx)) > (abs(blue_ny - blue_cy) + abs(blue_nx - blue_cx)))
						red_ny -= y_ar[i], red_nx -= x_ar[i];
					else
						blue_ny -= y_ar[i], blue_nx -= x_ar[i];
				}

				if (visited[red_ny][red_nx][blue_ny][blue_nx]) continue;

				red_que.push(make_pair(red_ny, red_nx));
				blue_que.push(make_pair(blue_ny, blue_nx));
				visited[red_ny][red_nx][blue_ny][blue_nx] = 1;

			}

		}

		if (result == 10)
			return -1;
		result++;

	}

	return -1;

}


int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 'R')
				ry = i, rx = j, arr[i][j] = '.';
			else if (arr[i][j] == 'B')
				by = i, bx = j, arr[i][j] = '.';
		}

	cout << bfs() << endl;

	return 0;
}