[백준/C++] 13460 구슬 탈출 2

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

13460번: 구슬 탈출 2

 

그냥 시뮬레이션 해서 구현하는 문제.

공이 네 방향으로 굴러갈 수 있으므로 bfs 기반이지만 공이 굴러가다가 알아서 방향을 트는 건 불가능하니까 약간의 처리를 해 주어야 한다.

 

처음 구상은 이랬다.

 

1 먼저 공이 굴러갈 방향을 찾는다(벽만 없다면 굴러갈 수 있다)

2 공을 가상으로 굴린다

공은 한 번 굴리면 그 방향으로만 쭉 가야 하니까, 차라리 목적지만 딱 찾아서 순간이동 하는 게 이득이라고 생각했다가 나중에 큰 오류를 낳았다

3 방문 처리를 한다

 

그러다가 여러 가지 이유로 틀렸는데,

 

1 빨간 구슬의 상태만 체크하면 안 된다

이 보드는 두 구슬이 상호작용을 하는 형태이므로, 빨간 구슬의 위치가 같아도 파란 구슬의 위치가 다르다면 다른 결과를 불러올 수 있다. 즉, 이 문제는 방문한다기보다는 두 구슬이 이루는 상태를 바라보는 관점이라고 하는 것이 더 적절한 것 같다.

 

2 굴러가는 도중에 구멍이 있을 수도 있다

지금 보면 되게 황당한 실수인데 구슬이 굴러간 곳에만 구멍이 있을 거라고 생각해서 굴러가다가 떨어질 거라는 생각을 못했다. 아마 저 순간이동이라는 단어에 꽂혀서 그런 게 아닐까 싶다(...)

3 굴러갈 수 있는지를 체크하는 건 두 구슬 모두 해당된다

사실 처음에는 빨간 구슬이 굴러갈 수 있을 때에만 구슬을 굴리도록 했다. 구슬이 굴러갈 수 없는 경우는 사방이 벽으로 둘러싸일 때밖에 없을 거라고 생각해서였다. 그런데 이렇게 빨간 구슬의 세 면이 모두 벽이고 옆에는 파란 구슬이 있을 때에는, 파란 구슬을 굴리고 나면 빨간 구슬도 굴릴 수 있게 된다.

 

XXXX

XRB.

XXXX

 

결국 파란 구슬이 굴러갈 수 있는지의 여부도 체크하는 것이 맞다. 1과 같이 두 구슬이 상호작용 하면서 보드의 상태를 만든다는 점에서, 빨간 구슬만 체크하는 건 어느 한 구슬의 움직임을 제한하는 셈이 되어 버리는 것 같기도 하다.

 

코드 구현 과정

1 기본적으로는 bfs의 맥락으로, 경로를 탐색하고 약간의 판별과정을 거쳐 큐에 삽입하는 흐름이다

2 다음 경로로 갈 수 있으면 일단 구슬을 가상으로 굴려 목적지를 찾는다

3 구르다가 중간에 떨어지는 건 blue_fall, red_fall 변수로 처리했다

4 두 구슬이 구르다가 만날 경우 선후관계에 따라 목적지를 조정해 주어야 하므로 굴리면서 카운트를 했다

5 목적지에 잘 도달했다면 보드의 상태를 저장한다

 

* 종료 조건

1 빨간 구슬만 떨어지는 경우 -> 별도로 처리함

2 움직일 수 없는 경우, 10번을 초과한 경우 -> 반복문의 실행 조건과 같음

 

뭐랄까, 내가 쓰긴 했지만 내 스타일의 코드는 아니다...ㅎㅎ

 

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

struct Node {
	pair<int, int> red;
	pair<int, int> blue;
	int count;
};

void input();
void bfs();

char board[10][10];
int px[4] = { -1, 0, 1, 0 };
int py[4] = { 0, -1, 0, 1 };
bool visited[10][10][10][10];
int n, m;
int ans = -1;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	input();
	bfs();
	cout << ans;
	return 0;
}

void input() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> board[i][j];
}

void bfs() {
	int rx, ry, bx, by;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (board[i][j] == 'R') {
				rx = i;
				ry = j;
			}
			else if (board[i][j] == 'B') {
				bx = i;
				by = j;
			}
		}
	}
	
	queue<Node> queue;
	queue.push({ { rx, ry }, { bx, by }, 0 });
	visited[rx][ry][bx][by] = true;

	while (!queue.empty() && queue.front().count < 10) {
		rx = queue.front().red.first;
		ry = queue.front().red.second;
		bx = queue.front().blue.first;
		by = queue.front().blue.second;
		int count = queue.front().count;

		for (int i = 0; i < 4; i++) {
			int nrx = rx + px[i];
			int nry = ry + py[i];
			int nbx = bx + px[i];
			int nby = by + py[i];
			
			if (board[nrx][nry] != '#' || board[nbx][nby] != '#') {// 굴릴 수 있나?
				bool red_fall = false;
				bool blue_fall = false;
				bool next = false;

				int rc = 0;
				int bc = 0;
				while (board[nbx][nby] != '#') { // 파란 구슬 굴림
					if (nbx == rx && nby == ry)
						next = true;
					if (board[nbx][nby] == 'O')
						blue_fall = true;
					nbx += px[i];
					nby += py[i];
					bc++;
				}
				nbx -= px[i];
				nby -= py[i];

				while (board[nrx][nry] != '#') { // 빨간 구슬 굴림
					if (nrx == bx && nry == by)
						next = true;
					if (board[nrx][nry] == 'O')
						red_fall = true;
					nrx += px[i];
					nry += py[i];
					rc++;
				}
				nrx -= px[i];
				nry -= py[i];



				if (next) { // 굴러가다가 만나는 경우에 대한 위치 조정
					if (rc > bc) {
						nrx -= px[i];
						nry -= py[i];
					}
					else {
						nbx -= px[i];
						nby -= py[i];
					}

				}


				if (!visited[nrx][nry][nbx][nby] && !blue_fall && !red_fall) { // 둘 다 안 떨어짐
					visited[nrx][nry][nbx][nby] = true;
					queue.push({ { nrx, nry }, { nbx, nby }, count + 1 });
				}

				if (!blue_fall && red_fall) { // 빨간 구슬만 떨어짐
					ans = count + 1;
					return;
				}
			}
		}
		queue.pop();
	}
}