(c++)백준 13460번: 구슬 탈출 2

www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

[풀이]

dfs를 사용하여 각각 방향마다 어떤 상태가 되는지 확인하는 방법으로 풀었다.

dfs를 10번 호출했으면 return해주었다.

빨간 구슬을 먼저 움직여주고, 파란 구슬을 움직여서 파란 구슬이 구멍에 빠졌으면 return, 빨간 구슬만 구멍에 빠졌으면 최소값을 갱신해주었다.

 

#include <iostream>
#include <algorithm>//min
#include <string>
using namespace std;

int N, M;
char Board[10][10];
const int dx[] = { -1,1,0,0 };
const int dy[] = { 0,0,-1,1 };
int Min = 987654321;

void dfs(int rx, int ry, int bx, int by, int cnt) {
	if (cnt > 10)
		return;
	//4방향으로 굴려보기
	for (int i = 0; i < 4; i++) {
		//빨간 구슬 먼저
		int nrx = rx;
		int nry = ry;
		int rmove = 0;
		//벽 만나기 전까지 굴리기
		while (Board[nrx][nry] != '#') {
			nrx += dx[i];
			nry += dy[i];
			//구멍에 빠지면 멈추기
			if (Board[nrx][nry] == 'O')
				break;
			rmove++;
		}
		//파란 구슬
		int nbx = bx;
		int nby = by;
		int bmove = 0;
		//벽 만나기 전까지 굴리기
		while (Board[nbx][nby] != '#') {
			nbx += dx[i];
			nby += dy[i];
			//구멍에 빠지면 멈추기
			if (Board[nbx][nby] == 'O')
				break;
			bmove++;
		}
		//파란 구슬 구멍에 빠졌으면 무효
		if (Board[nbx][nby] == 'O')
			continue;
		//빨간 구슬 구멍에 빠졌을 때
		if (Board[nrx][nry] == 'O') {
			Min = min(Min, cnt);
			return;
		}
		//구멍에 빠진 게 아니면 현재 좌표는 벽임
		nrx -= dx[i];
		nry -= dy[i];
		nbx -= dx[i];
		nby -= dy[i];

		//두 구슬이 겹치면
		if (nrx == nbx && nry == nby) {
			//빨간 구슬이 더 많이 움직였으면
			if (rmove > bmove) {
				nrx -= dx[i];
				nry -= dy[i];
			}
			//파란 구슬이 더 많이 움직였으면
			else {
				nbx -= dx[i];
				nby -= dy[i];
			}
		}
		dfs(nrx, nry, nbx, nby, cnt + 1);
	}
}

void solution() {
	cin >> N >> M;
	string s;
	int rx, ry;
	int bx, by;
	for (int i = 0; i < N; i++) {
		cin >> s;
		for (int j = 0; j < M; j++) {
			Board[i][j] = s[j];
			if (Board[i][j] == 'R')
				rx = i, ry = j;
			else if (Board[i][j] == 'B')
				bx = i, by = j;
		}
	}
	dfs(rx, ry, bx, by, 1);
	if (Min == 987654321)
		Min = -1;
	cout << Min << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solution();
	return 0;
}