[C++]BOJ 13460 - 구슬 탈출 2

처음에 시도했던 방법은 bfs에서 각 4가지 방향으로 기울였을 때 도달하는 지점의 좌표를 리턴하는 함수를 구현해 사용하는 것이었는데, 이후에 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 라는 문구를 보고 한참동안 뇌정지가 왔다.
어찌보면 당연하다. 구슬은 물리적으로 겹쳐질 수 없다.
구슬이 겹쳐지지 않는 경우를 알기 위해서 가장 쉽게 생각할 수 있는 방법은 구슬의 이동거리를 측정하는 것이다.

예를들어 #RB…….# 같은 간단한 구슬 탈출 장난감이 있다고 치자.
A를 빨간구슬과 파란구슬이 겹쳐진 신비롭고 놀라운 구슬이라고 가정하면, 위 상황에서 오른쪽으로 기울였을 때 #…….A# 가 된다.
이 때 R은 B보다 더 많은 거리를 이동했다. 이 말은 즉, “A는 B보다 왼쪽에 위치했었다” 라고 말할 수 있다.
따라서 A를 B로 바꾸고 R을 B왼쪽에 두면 #…….RB# 이런 형태가 돼서 겹쳐지지 않고 구슬을 이동시킬 수 있다.

그리고 bfs를 돌려서 각 방향으로 기울였을 때의 빨간구슬과 파란구슬의 위치를 탐색한다.
그리고 이전의 탐색 문제들과는 다르게 빨간 구슬이 한번 방문했던 위치라도 파란 구슬의 위치에 따라 결과가 달라지므로 방문처리를 위한 배열을 4차원 배열로 구성해 빨간구슬의 위치와 파란구슬의 위치를 동시에 체크해주어야 한다.

#include <iostream>
#include <queue>
using namespace std;
int n, m, rx, ry, bx, by, crx, cry, cbx, cby, cqc, cnt1, cnt2, v[12][12][12][12], dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0}, ans;
char arr[12][12];
queue<int> x1, x2, y1, y2, qc;
int main() {
	cin >> n >> m;
	for(int i = 0; i < n; i++) {
		scanf("%s", &arr[i]);
		for(int j = 0; j < m; j++)
			if(arr[i][j] == 'R') rx = j, ry = i;
			else if(arr[i][j] == 'B') bx = j, by = i;
	}
	x1.push(rx), x2.push(bx), y1.push(ry), y2.push(by), qc.push(0);
	v[rx][ry][bx][by] = 1;
	while(!x1.empty()) {
		rx = x1.front(); x1.pop();
		ry = y1.front(); y1.pop();
		bx = x2.front(); x2.pop();
		by = y2.front(); y2.pop();
		cqc = qc.front(); qc.pop();
		if(cqc > 10) {
			cout << "-1";
			return 0;
		}
		if(arr[ry][rx] == 'O') {
			cout << cqc;
			return 0;
		}
		for(int i = 0; i < 4; i++) {
			crx = rx; cry = ry; cbx = bx; cby = by; cnt1 = 0; cnt2 = 0;
			while(arr[cry + dy[i]][crx + dx[i]] != '#' && arr[cry][crx] != 'O') {
				crx += dx[i];
				cry += dy[i];
				cnt1++;
			}
			while(arr[cby + dy[i]][cbx + dx[i]] != '#' && arr[cby][cbx] != 'O') {
				cbx += dx[i];
				cby += dy[i];
				cnt2++;
			}
			if(crx == cbx && cry == cby) {
				if(arr[cby][cbx] == 'O') continue;
				if(cnt1 > cnt2) {
					crx -= dx[i];
					cry -= dy[i];
				} else {
					cbx -= dx[i];
					cby -= dy[i];
				}
			}
			if(v[crx][cry][cbx][cby]) continue;
			v[crx][cry][cbx][cby] = 1;
			x1.push(crx), x2.push(cbx), y1.push(cry), y2.push(cby), qc.push(cqc + 1);
		}
	}
	cout << "-1";
}