#13460번 구슬 탈출 2 (C++)

링크 : www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

문제의 핵심 포인트는 다음과 같다. 

1. 빨간공만 들어간 경우 

2. 빨간공과 파란공이 같이 들어간 경우

3. 파랑공만 들어간 경우

 

이 세가지를 구분하여 코드를 작성해야하는데, 구분에만 집중하다가는

코드가 너무 길어지고 필요없는 변수들이 여러번 생성될 수 있다. 

 

이 문제는 소스를 분석하며 해석하도록 하겠다.

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

int n=0, m=0, ry=0, rx=0, by=0, bx=0, my[4] = { 1,0,-1,0 }, mx[4] = { 0,1,0,-1 };
char arr[11][11];
bool visit[11][11][11][11] = { false };

int bfs() {
	queue <pair<pair<int, int>, pair<int, int>>> q;
	q.push(make_pair(make_pair(ry, rx), make_pair(by, bx)));
	visit[ry][rx][by][bx] = true;
	int ans = 0;
	while (!q.empty()) {
		int cnt = q.size();
		while (cnt--) {
			int ry_pos = q.front().first.first;
			int rx_pos = q.front().first.second;
			int by_pos = q.front().second.first;
			int bx_pos = q.front().second.second;
			q.pop();
			if (arr[ry_pos][rx_pos] == 'O' && arr[ry_pos][rx_pos] != arr[by_pos][bx_pos]) return ans;
			for (int i = 0; i < 4; i++) {
				int ry_new = ry_pos, rx_new = rx_pos, by_new = by_pos, bx_new = bx_pos;
				while (arr[ry_new + my[i]][rx_new + mx[i]] != '#' && arr[ry_new][rx_new] != 'O') {
					ry_new += my[i];
					rx_new += mx[i];
				}
				while (arr[by_new + my[i]][bx_new + mx[i]] != '#' && arr[by_new][bx_new] != 'O') {
					by_new += my[i];
					bx_new += mx[i];
				}
				if (ry_new == by_new && rx_new == bx_new) {
					if (arr[ry_new][bx_new] == 'O') continue; // 파랑공이 먼저 들어간 경우, 아래 코드들은 실행하지 않고 다시 while 조건문으로 돌아간다
					if (abs(ry_new-ry_pos) + abs(rx_new - rx_pos) > abs(by_new - by_pos) + abs(bx_new - bx_pos)) {
						ry_new -= my[i];
						rx_new -= mx[i];
					}
					else {
						by_new -= my[i];
						bx_new -= mx[i];
					}
				}
				if (visit[ry_new][rx_new][by_new][bx_new]) continue;
				q.push(make_pair(make_pair(ry_new, rx_new), make_pair(by_new, bx_new)));
				visit[ry_new][rx_new][by_new][bx_new] = true;
			}
		}
		if (ans == 10) return -1;
		ans++;
	}
	return -1;
}

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

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

1. 두개의 쌍을 이루는 큐를 만든다. 

2. 큐에 빨간공과 파란공의 값을 넣는다. 

3. 해당 위치들은 방문한 경험이 있는 것으로 표기한다. 

1. Q가 텅 빌때까지 while문을 진행한다. 

2. 동시에 Q의 사이즈를 기록하여, Q의 사이즈 만큼 한 번에 진행할 수 있도록 while문을 새운다.

(이에 관련된 자세한 해설은 마지막 '갯수 세기'에 한번 더 언급된다.)

3. 큐에 저장된 빨간공과 파란공의 값을 새로운 변수에 기록한다. 

4. 해당 큐의 값은 제거한다.

if (arr[ry_pos][rx_pos] == 'O' && arr[ry_pos][rx_pos] != arr[by_pos][bx_pos]) return ans;

1. 만약 해당 빨간공과 파랑공의 값이 서로 같지 않고 = 동시에 구멍에 들어가지 않고

빨간공이 구멍에 들어가면 누적된 이동값을 return하고 끝낸다.

1. 그렇지 않을 경우 상/하/좌/우로 이동을 시작한다. 

2. while문의 조건 해석은 다음과 같다.

   (1) 움직인 결과값이 #(벽)이 아닐때까지

   (2) 현재 위치 값이 구멍이 아닐때까지

둘의 의미는 다른 관계로, my[i]와 mx[i]가 있고 없고를 잘 구분해야한다. 

1. 만약 두 공의 위치가 같은 경우를 판별한다. 

2. 두 공 모두 구멍으로 들어갈 경우 -> arr[빨간공y][파란공x]가 '0'일 경우 -> continue를 실시한다. 

while문 - if 문- continue의 경우, continue 아래의 코드들로 넘어가지 않고 다시 while문의 조건문으로 넘어가게된다. 

3. 빨간공과 파란공의 이동한 값의 절대값을 구한다. 이때 더 크게 이동한 공(절대값의 합이 큼)이

다른 공보다 작은 값의 위치에 있다는 의미로, 해당 공은 한 단계 값을 낮추어준다. 

1. 새로운 위치값을 이미 이전에 방문한 경험이 있을 경우, continue를 실시한다. 

마찬가지로 while문 - if 문- continue의 경우, continue 아래의 코드들로 넘어가지 않고 다시 while문의 조건문으로 넘어가게된다.

3. 그렇지 않을 경우, 큐에 넣어주고 방문 표시를 해준다. 

1. 그렇게 for문이 종료되고, 큐 하나의 값에 대한 4방향의 새로운 위치값들이 누적된다. 

2. 큐에 다른 값이 있을 경우, 해당 값을 pop한다음 그 값에 대한 4방향의 새로운 위치들이 누적되는 값이 반복된다. 

3. 더 이상 큐에 저장된 값이 없을 경우, ans를 1개 증가시킨다. 

4. 이때 ans가 10일경우, 최대 횟수를 초과했으므로 -1을 리턴한다.