[백준 13460] 구슬탈출 2

https://www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

#include <cstdio>
#include <queue>
#include <cstring>
int N, M;
char board[10 + 2][10 + 2];
int rx, ry;
int bx, by;

struct _st
{
	int rx, ry;
	int bx, by;
	int move;
};
std::queue<_st> Q;
int visited[10 + 2][10 + 2][10 + 2][10 + 2];


void input()
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		scanf("%s", &board[i]);
		for (int j = 0; j < M; j++) {
			if (board[i][j] == 'R') {
				rx = i, ry = j;
				board[i][j] = '.';
			}
			else if (board[i][j] == 'B') {
				bx = i, by = j;
				board[i][j] = '.';
			}
		}
	}
}


int BFS()
{
	// dir
	// 우 좌 하 상
	int dir_x[4] = { 0, 0, 1, -1 };
	int dir_y[4] = { 1, -1, 0, 0 };


	// init
	Q = {};

	Q.push({ rx, ry, bx, by, 0 });
	visited[rx][ry][bx][by] = 1;

	while (!Q.empty()) {
		_st data = Q.front();
		//printf("[nowq]%d %d %d %d\n", data.rx, data.ry, data.bx, data.by);
		Q.pop();

		if (board[data.rx][data.ry] == 'O') return data.move;

		for (int p = 0; p < 4; p++) {
			int nrx = data.rx;
			int nry = data.ry;
			int nbx = data.bx;
			int nby = data.by;
			bool red_in_hole = false;
			bool blue_in_hole = false;

			if ((p == 0 && nry >= nby) || (p == 1 && nry <= nby) ||
				(p == 2 && nrx >= nbx) || (p == 3 && nrx <= nbx)) {
				// 빨간공 이동 
				while (1) {
					// 벽만남
					if (board[nrx + dir_x[p]][nry + dir_y[p]] == '#') break;
					nrx += dir_x[p];
					nry += dir_y[p];
					// 구멍만남 
					if (board[nrx][nry] == 'O') {
						red_in_hole = true;
						break;
					}
					// 빈칸임
					if (board[nrx][nry] == '.') continue;
				}

				// 파란공 이동 
				while (1) {
					// 벽만남
					if (board[nbx + dir_x[p]][nby + dir_y[p]] == '#') break;
					// 빨간공 만남 
					if (red_in_hole == false &&
						nbx + dir_x[p] == nrx && nby + dir_y[p] == nry) break;
					nbx += dir_x[p];
					nby += dir_y[p];
					// 구멍만남 
					if (board[nbx][nby] == 'O') {
						blue_in_hole = true;
						break;
					}
					// 빈칸임
					if (board[nbx][nby] == '.') continue;
				}
			}
			else if ((p == 0 && nry <= nby) || (p == 1 && nry >= nby) ||
				(p == 2 && nrx <= nbx) || (p == 3 && nrx >= nbx)) {
				// 파란공 이동 
				while (1) {
					// 벽만남
					if (board[nbx + dir_x[p]][nby + dir_y[p]] == '#') break;
					nbx += dir_x[p];
					nby += dir_y[p];
					// 구멍만남 
					if (board[nbx][nby] == 'O') {
						blue_in_hole = true;
						break;
					}
					// 빈칸임
					if (board[nbx][nby] == '.') continue;
				}
				// 빨간공 이동 
				while (1) {
					// 벽만남
					if (board[nrx + dir_x[p]][nry + dir_y[p]] == '#') break;
					// 파란공 만남 
					if (blue_in_hole == false &&
						nrx + dir_x[p] == nbx && nry + dir_y[p] == nby) break;
					nrx += dir_x[p];
					nry += dir_y[p];
					// 구멍만남 
					if (board[nrx][nry] == 'O') {
						red_in_hole = true;
						break;
					}
					// 빈칸임
					if (board[nrx][nry] == '.') continue;
				}
			}
			//printf("%d %d %d %d %d\n", p, nrx, nry, nbx, nby);
			if (blue_in_hole == true) continue;
			if (nrx == nbx && nry == nby) continue;
			if (visited[nrx][nry][nbx][nby]) continue;
			Q.push({ nrx, nry, nbx, nby, data.move + 1 });
			visited[nrx][nry][nbx][nby] = 1;
		}
	}
	return -1;
}




int main()
{
	input();
	int ans = BFS();
	if (ans == -1 || ans > 10) printf("%d\n", -1);
	else printf("%d\n", ans);
	return 0;
}

코드가 째꼼 더럽긴 하지만,,, 시험장 에서는 이렇게라도 풀어야 한다,,,

 

1. 처음에 틀린 이유는 "두 구슬이 동시에 움직이는" 것인데, 빨간색 공 움직이고 -> 파란색 공 움직이도록 순차적으로 구현했기 때문이다. 

2. 방향과 빨간공, 파란공 위치에 상관없이 하나의 while문으로 해결해 보려고 했는데 도저히 안돼서.. (머가리의 한계) 

각 방향별로 빨간공이 앞에있을 때, 파란공이 앞에있을 때를 나누어 루프를 구현해주었다.

3. "기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지" 라는 설명이 잘 이해되지 않았었는데, 테케 2번 보고 구슬이 하나라도 멈추면 기울임을 중단하는 것임을 깨달았다. 

그래서 먼저 이동한 구슬이 멈추었을 때, 만약 홀에 빠진 경우가 아니라면 나중에 이동한 구슬의 앞에 먼저 이동한 구슬이 있으면 기울임을 중단하도록 구현했다. 

4. 빨간 구슬만 방문처리하면 될 줄 알았는데, 파란 구슬도 함께 방문처리 해야하는 것을 뒤늦게 깨달았다. 

방문처리는 모든 루프를 빠져 나온 후, 조건에 맞는 상태를 Q에 push할 때 해준다.