BOJ_13460_구슬탈출(C++) [BFS]

PS 백준 소스 코드 모음 : https://github.com/kgw4073/Problem-Solving

---

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

13460번: 구슬 탈출 2

 본 문제를 읽어보면 딱 BFS로 풀어야 한다는 감이 올 것이다. 그러나 필자는 처음에 구슬을 구조체로 생각지 않고 map 자체에다가 그 정보를 저장하는 바람에 코드 길이가 12000 bytes가 되어 버렸다,,

 

개 망한 채점 현황

 이 문제는 그냥 일반 BFS와 동일하다. 다만 조건만 조금 까다로울 뿐이다.

 

 이 문제를 푸는 열쇠는 다음과 같다.

1. 구슬의 정보는 struct 로 저장한다.
2. visit 여부를 체크하는 배열을 구슬의 좌표가 될 수 있는 만큼 만들어야 한다. 10*10*10*10인 4차원 배열
3. 빨간 구슬과 파란 구슬 모두 map에는 빈 공간, 즉, ' . '으로 저장한다.
4. BFS를 할 때 트리의 depth의 계산을 용이하게 하는 테크닉이 필요하다. 

while (q.size()) {      int cnt = q.size();          while (cnt--)

 

 나머지 부분은 주석에 상세히 설명했으니 참고하면 될 것이다.

#include <iostream>
#include <queue>

using namespace std;

char map[10][10];
int n, m;
struct ball {
	int ry, rx, by, bx;
};

ball current;
bool visit[10][10][10][10];
int dy[] = { 0, 1, 0, -1 };
int dx[] = { 1, 0, -1, 0 };

void bfs() {
	queue<ball> q;
	visit[current.ry][current.rx][current.by][current.bx] = true;

	// finishFlag는 빨간 색 구슬만 들어갔을 때 세팅된다.
	bool finishFlag = false;
	q.push(current);
	int count = 0;

	// 다음 이중 while문은 트리 bfs시에 depth를 계산을 용이하게 한다.
	while (q.size()) {
		int cnt = q.size();
		while (cnt--) {
			ball cur = q.front();
			q.pop();
			// 큐에서 꺼내봤더니 빨간 구슬이 구멍에 들어갔다면 finish
			if (map[cur.ry][cur.rx] == 'O') {
				finishFlag = true;
				break;
			}
			for (int dir = 0; dir < 4; dir++) {
				// 0번은 빨간색, 1번은 파란색
				// 각각 구멍에 들어갔는지 안 들어갔는지 저장
				bool outFlag[2] = { false, };
				// 이동 거리. 일단 통과해서 이동한다고 가정하기 때문에
				// 같은 위치에 도달했을 때, 더 먼 이동거리인 구슬이 한 칸 back 해야 함.
				int movingDistance[2] = { 0, };
				vector<pair<int, int>> v;
				v.push_back({ cur.ry, cur.rx });
				v.push_back({ cur.by, cur.bx });

				for (int color = 0; color < 2; color++) {
					while (map[v[color].first + dy[dir]][v[color].second + dx[dir]] != '#') {
						movingDistance[color]++;
						v[color].first += dy[dir];
						v[color].second += dx[dir];

						// 구멍에 들어간다면 outFlag를 세팅하고 나감
						if (map[v[color].first][v[color].second] == 'O') {
							outFlag[color] = true;
							break;
						}
					}
				}
				// 파란색이 들어갔으면 큐에 안 넣음
				if (outFlag[1]) continue;

				if (v[0].first == v[1].first && v[0].second == v[1].second) {
					if (movingDistance[0] > movingDistance[1]) {
						v[0].first -= dy[dir];
						v[0].second -= dx[dir];
					}
					else {
						v[1].first -= dy[dir];
						v[1].second -= dx[dir];
					}
				}
				// 이미 방문했던 위치라면 큐에 넣을 필요가 없음
				if (visit[v[0].first][v[0].second][v[1].first][v[1].second]) {
					continue;
				}
				visit[v[0].first][v[0].second][v[1].first][v[1].second] = true;

				ball next = { v[0].first, v[0].second, v[1].first, v[1].second };
				q.push(next);
			}
		}
		if (finishFlag) break;
		count++;
		if (count > 10) break;
	}
	if (finishFlag) {
		cout << count;
	}
	else {
		cout << -1;
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			char c;
			cin >> c;
			// R 혹은 B이면 해당 위치의 좌표만 저장하고 map은 .으로 저장한다.
			if (c == 'R') {
				current.ry = i;
				current.rx = j;
				c = '.';
			}
			else if (c == 'B') {
				current.by = i;
				current.bx = j;
				c = '.';
			}
			map[i][j] = c;
		}
	}
	bfs();
}