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

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

13459번: 구슬 탈출

 

까다로운 문제였습니다. 10번까지 검증하기 때문에 dfs가 아니라 bfs로 구현해야 했습니다.

 

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

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

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

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

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

 

 

정답코드입니다.

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;

int n = 0, m = 0;
char arr[12][12];

int r_y, r_x;
int b_y, b_x;
int result = 0;

int y_ar[4] = { 0,0,1,-1 };
int x_ar[4] = { 1, -1, 0, 0 };
bool visited[12][12][12][12] = { 0, };

int bfs() {

	queue <pair <int, int>> b_que;
	queue <pair <int, int>> r_que;
	b_que.push(make_pair(b_y, b_x));
	r_que.push(make_pair(r_y, r_x));

	result = 0; // 0으로 초기화
	while (!b_que.empty()) {
		int sized = b_que.size();

		while (sized--) {
			int red_y = r_que.front().first;
			int red_x = r_que.front().second;
			int blue_y = b_que.front().first;
			int blue_x = b_que.front().second;
			r_que.pop(), b_que.pop();


			if (arr[red_y][red_x] == 'O') // O에 있을때
				return result;
			
			for (int i = 0; i < 4; i++) {
				int nextred_y = red_y;
				int nextred_x = red_x;
				int nextblue_y = blue_y;
				int nextblue_x = blue_x;

				while (arr[nextred_y + y_ar[i]][nextred_x + x_ar[i]] != '#' && arr[nextred_y][nextred_x] != 'O') {
					nextred_y += y_ar[i];
					nextred_x += x_ar[i];
				}
				while (arr[nextblue_y + y_ar[i]][nextblue_x + x_ar[i]] != '#' && arr[nextblue_y][nextblue_x] != 'O') {
					nextblue_y += y_ar[i];
					nextblue_x += x_ar[i];
				}
				if (nextred_y == nextblue_y && nextred_x == nextblue_x) {
					if (arr[nextred_y][nextred_x] == 'O') continue; // 이 경로는 가면 안되는 경로라서 continue로 넘겨줌 	

					// 더 많이 이동한쪽이 진짜 자기 위치  
					if ((abs(nextred_y - red_y) + abs(nextred_x - red_x)) > (abs(nextblue_y - blue_y) + abs(nextblue_x - blue_x)))
						nextred_y -= y_ar[i], nextred_x -= x_ar[i];
					else
						nextblue_y -= y_ar[i], nextblue_x -= x_ar[i];
						
				}

				if (visited[nextred_y][nextred_x][nextblue_y][nextblue_x]) continue; //기존에 방문했다면 
				r_que.push(make_pair(nextred_y,nextred_x));
				b_que.push(make_pair(nextblue_y,nextblue_x));
				visited[nextred_y][nextred_x][nextblue_y][nextblue_x] = 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] == 'B')
				b_y = i, b_x = j, arr[i][j] = '.';
			else if (arr[i][j] == 'R')
				r_y = i, r_x = j, arr[i][j] = '.';
		}


	if (bfs() == -1)
		cout << 0 << endl;
	else
		cout << 1 << endl;


	
	return 0;
}

스스로 부족한 것을 많이 느꼈습니다. 구슬탈출2를 풀어보면서 더욱 연습할 계획입니다. 

 

 

아래는 dfs를 통해 구현한 코드입니다.

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

int n, m;
string arr[10];
bool result = 0;
int y_ar[4] = { 0,1,0,-1 };
int x_ar[4] = { -1,0,1,0 };

void dfs(int cnt, int ry, int rx, int by, int bx) {
	if (cnt == 10)
		return;
	if (result)
		return;

	for (int i = 0; i < 4; i++) {

		int nry = ry, nrx = rx;
		int nby = by, nbx = bx;
		bool blue = false, red = false;
		while (1) {

			if (arr[nry + y_ar[i]][nrx + x_ar[i]] == '.') {
				nry += y_ar[i];
				nrx += x_ar[i];
			}
			else if (arr[nry + y_ar[i]][nrx + x_ar[i]] == 'O') {
				nry += y_ar[i];
				nrx += x_ar[i];
				red = true;
				break;
			}
			else if (arr[nry + y_ar[i]][nrx + x_ar[i]] == '#') {
				break;
			}
		}

		while (1) {
			if (arr[nby + y_ar[i]][nbx + x_ar[i]] == '.') {
				nby += y_ar[i];
				nbx += x_ar[i];
			}
			else if (arr[nby + y_ar[i]][nbx + x_ar[i]] == 'O') {
				nby += y_ar[i];
				nbx += x_ar[i];
				blue = true;
				break;
			}
			else if (arr[nby + y_ar[i]][nbx + x_ar[i]] == '#') {
				break;
			}
		}

		if (blue == true)
			continue;
		if (red == true) {
			result = true;
			return;
		}

		if (nrx == nbx && nry == nby) {			//포개진 경우
			if (i == 0) {
				if (rx > bx) 	nrx += 1;	//빨간공이 밑에 있었던 경우
				else			nbx += 1;
			}
			else if (i == 1) {
				if (ry > by)	nby -= 1;		//파란공이 더 왼쪽에서 시작한 경우
				else			nry -= 1;
			}
			else if (i == 2) {
				if (rx > bx)		nbx -= 1;		//파란공이 더 위에서 시작
				else				nrx -= 1;
			}
			else if (i == 3) {
				if (ry > by)		nry += 1;		//빨간공이 더 오른쪽에서 시작
				else				nby += 1;
			}
		}

		dfs(cnt + 1, nry, nrx, nby, nbx);




	}

}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m;

	int ry, rx, by, bx;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		for (int j = 0; j < m; 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] = '.';
			}
		}
	}

	dfs(0, ry, rx, by, bx);
	cout << result << endl;

	return 0;
}