[BOJ 13460] 구슬 탈출2 (C++)

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

13460번: 구슬 탈출 2

#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <cstring>
using namespace std;

int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };

string graph[10];
bool visited[10][10][10][10];		

class Info {
public:
	int ry, rx, by, bx;
	int cnt;
	Info(int ry, int rx, int by, int bx, int cnt): ry(ry), rx(rx), by(by), bx(bx), cnt(cnt)
	{}
};

int sol() {
	int N, M;
	cin >> N >> M;
	pair<int, int> red;
	pair<int, int> blue;
	pair<int, int> hole;
	int answer = 0;
	memset(visited, false, sizeof(visited));
	for (int i = 0; i < N; i++) {
		cin >> graph[i];
		for (int j = 0; j < M; j++) {
			if (graph[i][j] == 'B')
				blue = make_pair(i, j);
			else if (graph[i][j] == 'R')
				red = make_pair(i, j);
		}
	}

	queue<Info> q;
	q.push(Info(red.first, red.second, blue.first, blue.second, 0));
	visited[red.first][red.second][blue.first][blue.second] = true;		//이 case를 탐색한다
	while (!q.empty()) {
		Info now = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ry = now.ry;
			int rx = now.rx;
			int by = now.by;
			int bx = now.bx;
			//일단 다 굴려준다
			while (graph[by + dy[i]][bx + dx[i]] != '#') {
				by += dy[i];
				bx += dx[i];
				if (graph[by][bx] == 'O') {
					break;
				}
			}
			while (graph[ry + dy[i]][rx + dx[i]] != '#') {
				ry += dy[i];
				rx += dx[i];
				if (graph[ry][rx] == 'O') {
					break;
				}
			}
			//blue가 hole에 있을 경우 탐색x
			if (graph[by][bx] == 'O')
				continue;
			//red가 hole에 있을 경우 10번 이하인지 체크하고 그러면 정답 리턴, 10번 넘으면 -1 리턴
			if (graph[ry][rx] == 'O') {
				if (now.cnt + 1 <= 10)
					return now.cnt + 1;
				return -1;
			}
			if (by == ry && bx == rx) {					//서로 겹칠 경우 좌표 재조정
				switch (i) {
				case 0:
					if (now.ry > now.by)
						ry += 1;
					else
						by += 1;
					break;
				case 1:
					if (now.ry > now.by)
						by -= 1;
					else
						ry -= 1;
					break;
				case 2:
					if (now.rx > now.bx)
						rx += 1;
					else
						bx += 1;
					break;
				case 3:
					if (now.rx > now.bx)
						bx -= 1;
					else
						rx -= 1;
					break;
				}
			}
			if (!visited[ry][rx][by][bx]) {		//미방문 case이면
				q.push(Info(ry, rx, by, bx, now.cnt + 1));
				visited[ry][rx][by][bx] = true;		//이 case 탐색한다
			}
		}
	}
	return -1;
}

int main() {
	cout << sol() << "\n";
	return 0;
}

나름 복잡해 보여 고민을 많이 한 문제.

 

BFS 탐색이고, 이 문제의 포인트는 1. 빨간 공과 파란 공의 위치가 겹칠 경우 위치를 재조정해주는 것 (이 부분때문에 조건을 복잡하게 세워서 케이스 나누고.. 복잡하게 풀려고 시도했었다..) 2. 빨간 공, 파란 공 위치가 겹치든 말든 일단 굴려주는 것 3. visited[red.y][red.x][blue.y][blue.x] 이런 식으로 방문했던 상태를 표시해주는 것

 

일단 빨간 공, 파란 공을 벽을 만날 때 혹은 Hole을 만날 때까지 굴려준다.

만약 파란 공이 hole에 있으면 그 case는 탐색하지 않으므로 다시 다른 것을 탐색.

빨간 공이 Hole에 있으면 10번 이하인지 체크하고 답 반환.

빨간 공, 파란 공이 같은 위치에 있는 경우, 겹치는 case 이므로 위치를 재조정해준다. R B # 이런 순서대로 있었으면 그 순서대로 다시 재조정해주기. (여기서 switch..case 문을 썼는데, 다른 분들의 코드를 보니 움직이는 횟수를 count 해줘서 움직이는 횟수가 많았던 쪽을 y-dy[i], x-dx[i] 해주면 간단하게 구현 가능하다.

visited[빨간공][파란공] 해주어서 해당 상태를 이미 탐색한 적이 있으면 탐색x, 탐색한 적이 없으면 큐에 넣어줘서 탐색 대상으로 삼는다.