BOJ 13460 구슬 탈출 2

사용한 알고리즘

알고리즘 설명

BFS를 이용하여 상하좌우로 공을 움직여본다.
공을 움직였을때, 빨간색공은 구멍에 빠지고, 파란색 공은 빠지지 않는 경우를 찾으면 성공이다.
공을 옮길때에 빨간색 공을 옮긴 뒤에 파란색을 옮기는 형태로 진행하였고, 파란색 공을 옮길 때에 옮기는 방향에 빨간색 공이 있으면 그 전 장소로 매핑해준다.

풀이

// baekjon 13460 yechan
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int MAX_N=11;
const int dir[4][2] = {{0,1}, {0,-1}, {1,0},{-1,0}};
typedef pair<int, int> P;

struct Balls{
	P redBall, blueBall;
	Balls(){}
	Balls(int rx, int ry, int bx, int by) {
		redBall.first = rx;
		redBall.second = ry;
		blueBall.first = bx;
		blueBall.second = by;
	}
};

int N, M;

char board[MAX_N][MAX_N];

int bfs(){
	queue<Balls> q;
	Balls start;
	for (int i=0; i<N; i++) {
		for (int j=0; j<M; j++) {
			if (board[i][j] == 'R') {
				board[i][j]='.';
				start.redBall.first=i, start.redBall.second=j;
			}
			if (board[i][j] == 'B') {
				board[i][j]='.';
				start.blueBall.first=i, start.blueBall.second=j;
			}
		}
	}
	q.push(start);

	int trial = 1;
	while (!q.empty()) {
		int qSize = q.size();
		while (qSize--) {
			int cur_rx = q.front().redBall.first;
			int cur_ry = q.front().redBall.second;
			int cur_bx = q.front().blueBall.first;
			int cur_by = q.front().blueBall.second;
			q.pop();

			for (int d=0; d<4; d++) {
				int tmp_rx = cur_rx;
				int tmp_ry = cur_ry;
				int tmp_bx = cur_bx;
				int tmp_by = cur_by;

				bool bflag=false, rflag=false;
				for (int i=0; i<=MAX_N+1; i++) {
					int next_rx = tmp_rx + dir[d][0];
					int next_ry = tmp_ry + dir[d][1];
					if (!rflag && board[next_rx][next_ry] == 'O') {
						rflag=true;
						tmp_rx = -1;
						tmp_ry = -1;
					}
					if (!rflag && board[next_rx][next_ry] == '.' && !(tmp_bx==next_rx && tmp_by==next_ry)) {
						tmp_rx = next_rx;
						tmp_ry = next_ry;
					}

					int next_bx = tmp_bx + dir[d][0];
					int next_by = tmp_by + dir[d][1];
					if (board[next_bx][next_by] == 'O') {
						bflag=true;
						break;
					}
					if (board[next_bx][next_by] == '.' && !(tmp_rx==next_bx && tmp_ry==next_by)) {
						tmp_bx = next_bx;
						tmp_by = next_by;
					}
				}
				if (bflag) continue;
				if (rflag && !bflag) return trial;
				q.push(Balls(tmp_rx, tmp_ry, tmp_bx, tmp_by));
			}
		}
		trial++;
		if (trial == 11) break;
	}
	return -1;
}

int main() {
	scanf("%d%d", &N, &M);
	for (int i=0; i<N; i++)
		scanf("%s", board[i]);
	printf("%d\n", bfs());
	return 0;
}