BOJ 백준 13460 구슬 탈출2 콜라한캔

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

< 구슬 탈출 2 >

1. 빨간 구슬과 파란 구슬 중 어떤 구슬을 먼저 굴릴 지 판별한다.

2. 상, 하, 좌, 우 방향으로 판을 기울여 구슬을 굴린다.

2 - 1. 이전에 굴린 방향이나, 굴린 방향의 반대 방향 ( UP - DOWN / LEFT - RIGHT )의 경우 고려하지 않는다.

2 - 2. 판을 기울였는데, 빨간 구슬과 파란 구슬 둘 다 움직였을 경우 고려하지 않는다.

3. 굴린 결과를 다시 재귀로 보내준다.

4. 파란 구슬이 들어가지 않고, 횟수가 10번이 넘어가지 않는 상황에서 빨간 구슬이 들어갔을 때 판을 기울인 횟수를 저장한다.

 1번 조건. 상, 하, 좌, 우 4가지 경우로 나누어 생각해보면 된다.

판을 기울여서 구슬들을 상, 하로 굴려줄 경우에는 빨간 구슬과 파란 구슬의 x값을 비교하면 된다.

위로 굴리는 경우에는 x값이 더 적은 구슬 (맵에서 더 위에 있는 구슬) 부터,

아래로 굴리는 경우에는 x값이 더 큰 구슬 (맵에서 더 아래에 있는 구슬) 부터 굴려준다.

마찬가지로 좌, 우로 굴려줄 경우에는 y값을 비교해주면 된다.

 2번 조건. 여러가지 방법이 있겠지만, 내 코드에서는 각 방향에 따라 for문을 통해 판을 기울여 구슬을 굴려주고 있다.

- 현재 구슬이 굴러갈 방향이 빈칸인지 확인한 뒤에, 빈칸일 경우 계속 굴려준다.번

- 만약 구슬이 'O'에 도착했을 경우, O 다음이 빈칸이어도 멈출 수 있도록 break를 통해 for문을 나온다.

 3번 조건. 구슬들이 굴러간 위치와 방글 굴린 방향, 판을 기울인 횟수 + 1을 재귀로 다시 보내준다.

재귀를 한바탕 돌고 돌아왔을 때, 맵을 다시 원상태로 돌려주어야 한다.

예를 들어  # . . . R # 에서 좌로 굴려주면 # R . . . # 이 되는데, 재귀가 끝나 돌아왔을 경우에는 다시 # . . . R # 로 복귀시켜주어야 한다.

이 방법으로 맵 전체를 복사하는 방식도 있지만 이는 n * m 의 시간과 공간이 사용되기 때문에 비효율적이다.

따라서 cur_red와 cur_blue, next_red와 next_blue의 char 변수를 이용하였다.

현재 구슬의 위치의 문자를 cur_red와 cur_blue에 저장해주고, 굴러간 위치의 문자를 next_red와 next_blue에 저장해준다.

ex) 빨간 구슬만 고려한 경우 ( 파란 구슬도 결국 동일한 방식 )

1 2 3 4 5

# .  .  R #     먼저 cur_red에 4번 R을 저장해준 뒤 판을 기울인다. ( 좌로 기울이는 경우 )

좌로 기울일 경우 R은 2번 위치에 가게 되는데, 이 때 2번 위치 '.'을 next_red에 저장해준다.

cur_red와 next_red에 모두 저장했다면 swap을 통해 # R . . # 로 만들어주고 재귀를 돌린다.

재귀에서 빠져나왔을 경우, swap을 2번 호출하여 2번 위치에 next_red를 저장해주고 4번 위치에 cur_red를 저장해주면 원상태로 복귀한다.

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#define SIZE 11
#define INF 1000000000

#define UP 0
#define LT 1
#define DOWN 2
#define RT 3

using namespace std;
int n, m;
int ex, ey;
char map[SIZE][SIZE];
int iMin = INF;

inline void swap(char* a, char* b) {
	char temp = *a;
	*a = *b;
	*b = temp;
}

bool redFirst(int rx, int ry, int bx, int by, int dir) {
	if (dir == UP) return rx < bx;
	else if (dir == LT) return ry < by;
	else if (dir == DOWN) return rx > bx;
	else if (dir == RT) return ry > by;
}

void move(int &x, int &y, int dir) {
	int i;
	if (dir == UP) {
		for (i = x - 1; map[i][y] == '.' || map[i][y] == 'O'; i--) {
			x--;
			if (map[x][y] == 'O') break;
		}
	}
	else if (dir == LT) {
		for (i = y - 1; map[x][i] == '.' || map[x][i] == 'O'; i--) {
			y--;
			if (map[x][y] == 'O') break;
		}
	}
	else if (dir == DOWN) {
		for (i = x + 1; map[i][y] == '.' || map[i][y] == 'O'; i++) {
			x++;
			if (map[x][y] == 'O') break;
		}
	}
	else if (dir == RT) {
		for (i = y + 1; map[x][i] == '.' || map[x][i] == 'O'; i++) {
			y++;
			if (map[x][y] == 'O') break;
		}
	}
}

void solution(int rx, int ry, int bx, int by, int prevDir, int num) {
	if (num > 10) return;
	if (bx == ex && by == ey) return;
	if (rx == ex && ry == ey) {
		if (iMin > num) iMin = num;
		return;
	}

	for (int i = 0; i < 4; i++) {
		if (prevDir != -1 && i == prevDir) continue;
		if (prevDir != -1 && i == (prevDir + 2) % 4) continue;
		
		char cur_red = map[rx][ry];
		char cur_blue = map[bx][by];
		int next_rx = rx;
		int next_ry = ry;
		int next_bx = bx;
		int next_by = by;

		if (redFirst(rx, ry, bx, by, i)) {
			move(next_rx, next_ry, i);
			char next_red = map[next_rx][next_ry];
			if (next_red == 'O') map[rx][ry] = '.';
			else swap(&map[rx][ry], &map[next_rx][next_ry]);

			
			move(next_bx, next_by, i);
			char next_blue = map[next_bx][next_by];
			if (next_blue == 'O') map[bx][by] = '.';
			else swap(&map[bx][by], &map[next_bx][next_by]);

			if (rx == next_rx && ry == next_ry && bx == next_bx && by == next_by) continue;

			solution(next_rx, next_ry, next_bx, next_by, i, num + 1);
			swap(&map[rx][ry], &cur_red);
			swap(&map[next_rx][next_ry], &next_red);
			swap(&map[bx][by], &cur_blue);
			swap(&map[next_bx][next_by], &next_blue);
		}
		else {
			move(next_bx, next_by, i);
			char next_blue = map[next_bx][next_by];
			if (next_blue == 'O') map[bx][by] = '.';
			else swap(&map[bx][by], &map[next_bx][next_by]);

			
			move(next_rx, next_ry, i);
			char next_red = map[next_rx][next_ry];
			if (next_red == 'O') map[rx][ry] = '.';
			else swap(&map[rx][ry], &map[next_rx][next_ry]);

			if (rx == next_rx && ry == next_ry && bx == next_bx && by == next_by) continue;

			solution(next_rx, next_ry, next_bx, next_by, i, num + 1);
			swap(&map[rx][ry], &cur_red);
			swap(&map[next_rx][next_ry], &next_red);
			swap(&map[bx][by], &cur_blue);
			swap(&map[next_bx][next_by], &next_blue);
		}
	}
}

int main() {
	int rx = 0, ry = 0, bx = 0, by = 0;
	scanf("%d %d", &n, &m);

	for (int i = 0; i < n; i++) {
		scanf("%s", map[i]);
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 'R') {
				rx = i;
				ry = j;
			}
			else if (map[i][j] == 'B') {
				bx = i;
				by = j;
			}
			else if (map[i][j] == 'O') {
				ex = i;
				ey = j;
			}
		}
	}
	solution(rx, ry, bx, by, -1, 0);
	printf("%d\n", iMin == INF ? -1 : iMin);

	return 0;
}