C++:: boj 13460 <구슬 탈출 2>

dfs를 사용하여 구슬이 탈출하는 최단 경로 횟수를 반환하는 문제이다. 주의해야 할 점이 조금 있는 문제이다.
먼저 두 공이 곂칠수 없다는 점을 유의해야하며 무슨 공을 먼저 움직이는지도 주의해 주어야 한다.
예시로 RB와 같은 형식으로 맵에 들어오고 왼쪽으로 이동했을때 는 R을 먼저 이동해야한다.
그리고 최대 10번까지가 정답이므로 그점도 주의하자.

#include <iostream>
#include <vector>
using namespace std;

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

pair<int,int> moveBall(int dir, int nx, int ny, char ball, vector<string>& board) {
	board[nx][ny] = '.';
	while (1) {
		nx += dx[dir];
		ny += dy[dir];
		if (board[nx][ny] == 'O') {// 탈출하면 따로 표시 X
			return {nx, ny};
		}
		if (board[nx][ny] != '.') {
			break;
		}
	}
	board[nx - dx[dir]][ny - dy[dir]] = ball;// 이동위치에 표기
	return {nx - dx[dir], ny - dy[dir]};
}

void dfs(int cnt, pair<int,int> r_pos, pair<int,int> b_pos, vector<string>& board) {
	if (cnt > 9 || (res != -1 && cnt >= res)) return ;
	for (int dir=0; dir<4; dir++) {
		pair<int,int> r_npos, b_npos;
        // 공 움직이는 순서
		if ((dir == 0 && r_pos.first > b_pos.first)   ||
			(dir == 1 && r_pos.second < b_pos.second) ||
			(dir == 2 && r_pos.first < b_pos.first)   ||
			(dir == 3 && r_pos.second > b_pos.second)) {
			b_npos = moveBall(dir, b_pos.first, b_pos.second, 'B', board);
			r_npos = moveBall(dir, r_pos.first, r_pos.second, 'R', board);
		} else {
			r_npos = moveBall(dir, r_pos.first, r_pos.second, 'R', board);
			b_npos = moveBall(dir, b_pos.first, b_pos.second, 'B', board);
		}
        // 이동한게 이전과 동일하다면 굳이 더 할 필요 X
		if (r_pos == r_npos && b_pos == b_npos) continue;
		// 공이 둘따 빠지면
		if (board[b_npos.first][b_npos.second] == 'O' && board[r_npos.first][r_npos.second] == 'O') {
			board[r_pos.first][r_pos.second] = 'R';
			board[b_pos.first][b_pos.second] = 'B';
			continue;
		}
        // 파란공만 빠지면
		if (board[b_npos.first][b_npos.second] == 'O') {
			board[r_npos.first][r_npos.second] = '.';
			board[r_pos.first][r_pos.second] = 'R';
			board[b_pos.first][b_pos.second] = 'B';
			continue;
		}
        // 빨간공만 빠지면
		if (board[r_npos.first][r_npos.second] == 'O') {
			board[b_npos.first][b_npos.second] = '.';
			board[r_pos.first][r_pos.second] = 'R';
			board[b_pos.first][b_pos.second] = 'B';
			res = cnt + 1;
			break ;
		}

		dfs(cnt + 1, r_npos, b_npos, board);

		board[r_npos.first][r_npos.second] = '.';
		board[b_npos.first][b_npos.second] = '.';
		board[r_pos.first][r_pos.second] = 'R';
		board[b_pos.first][b_pos.second] = 'B';
	}
}

int main() {
	cin >> n >> m;
	vector<string> board(n, string(m, ' '));
	pair<int,int> r_pos, b_pos;
	for (int i=0; i<n; i++) {
		for (int j=0; j<m; j++) {
			cin >> board[i][j];
			if (board[i][j] == 'R') {
				r_pos = {i, j};
			} else if (board[i][j] == 'B') {
				b_pos = {i, j};
			}
		}
	}
	dfs(0, r_pos, b_pos, board);
	cout << res << "\n";
}