백준 13460 : 구슬 탈출 2

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

13460번: 구슬 탈출 2

[ 문제풀이 ]

삼성 기출문제는 대부분 시뮬레이션 or 완전 탐색 문제이다. 이 문제는 매번 새로운 맵을 만들어주면서 모든 경우의 수를 확인하면 해결할 수 있다.

​주의해야 할 점은 빨간 구슬과 파란 구슬 중 어떤 구슬을 먼저 움직이느냐를 판단하는 것이다. 현재 map이 다음과 같은 형태라고 하자.

# # # # #
#     O #
# B     #
# R     #
# # # # #

만약 위쪽으로 기울이는 경우 어떤 구슬부터 움직여야 할까?

위쪽에 가까운 파란 구슬(B)부터 위로 움직인 후 빨간 구슬(R)을 위쪽으로 움직여야 할 것이다. 이처럼 기울이는 방향에 더 가까운 구슬부터 움직여야 한다.

위쪽으로 기울이는 경우 : 빨간 구슬이 더 위쪽에 있는 경우 => 1. 빨간 구슬, 2. 파란 구슬
                       파란 구슬이 더 위쪽에 있는 경우 => 1. 파란 구슬, 2. 빨간 구슬

왼쪽으로 기울이는 경우 : 빨간 구슬이 더 왼쪽에 있는 경우 => 1. 빨간 구슬, 2. 파란 구슬
                       파란 구슬이 더 왼쪽에 있는 경우 => 1. 파란 구슬, 2. 빨간 구슬

아래쪽으로 기울이는 경우 : 빨간 구슬이 더 아래쪽에 있는 경우 => 1. 빨간 구슬, 2. 파란 구슬
                         파란 구슬이 더 아래쪽에 있는 경우 => 1. 파란 구슬, 2. 빨간 구슬

오른쪽으로 기울이는 경우 : 빨간 구슬이 더 오른쪽에 있는 경우 => 1. 빨간 구슬, 2. 파란 구슬
                         파란 구슬이 더 오른쪽에 있는 경우 => 1. 파란 구슬, 2. 빨간 구슬

마지막으로 시간을 조금 더 줄일 수 있는 방법이다.

첫 번째는 4방향을 모두 탐색할 필요가 없다. 이전에 왔던 방향이나 정반대 방향은 이미 확인한 방향이기 때문이다.

​두 번째는 현재 움직인 횟수가 정답보다 크거나 같은 경우도 탐색할 필요가 없다. 더 탐색해봤자 최소 횟수가 성립하지 않기 때문이다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;

	static int N, M, answer;
	
	static int[][] dir = {{-1,0}, {0,-1}, {1,0}, {0,1}};

	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		int[] red = new int[2];
		int[] blue = new int[2];
		char[][] map = new char[N][M];
		
		for (int i = 0; i < N; ++i) {
			String str = br.readLine();
			for (int j = 0; j < M; ++j) {
				map[i][j] = str.charAt(j);
				
				if (map[i][j] == 'R') {
					red[0] = i;
					red[1] = j;
				} else if (map[i][j] == 'B') {
					blue[0] = i;
					blue[1] = j;
				}
			}
		}

		answer = 100;

		simulation(-1, 1, map, red, blue);

		bw.write((answer == 100 ? -1 : answer) + "\n");
		bw.flush();bw.close();br.close();
	}

	public static void simulation(int before_Dir, int cnt, char[][] map, int[] red, int[] blue) {
		if (cnt > 10) return;
		
		char[][] temp = new char[N][M];
		int[] red2 = new int[2];
		int[] blue2 = new int[2];
		boolean[] finish = new boolean[2];
		
		for (int d = 0; d < 4; ++d) {
			//이전에 왔던 방향 or 정반대 방향은 확인할 필요 없음
			if (before_Dir != -1 && (d == before_Dir || d == (before_Dir + 2) % 4)) continue;
			
			//현재 움직인 횟수가 정답보다 작거나 같으면 확인할 필요 없음
			if (answer <= cnt) continue;
			
			//이동하기 때문에 새로운 맵을 만들어줌
			copyMap(map, temp);
			
			red2[0] = red[0]; red2[1] = red[1];
			blue2[0] = blue[0]; blue2[1] = blue[1];
			
			finish[0] = false; finish[1] = false; //빨간, 파란 구슬이 구멍에 빠졌는지 확인
			
			//위로 기울이는 경우
			if (d == 0) {
				//파란 구슬이 빨간 구슬보다 위쪽에 위치할 경우 파란 구슬부터 움직여줌
				if (red[0] >= blue[0]) {
					while (temp[blue2[0] + dir[d][0]][blue2[1]] != '#') {
						temp[blue2[0]][blue2[1]] = '.';
						blue2[0] += dir[d][0];
						
						if (temp[blue2[0]][blue2[1]] == 'O') {
							finish[1] = true;
							break;
						}

						temp[blue2[0]][blue2[1]] = 'B';
					}
					
					while (temp[red2[0] + dir[d][0]][red2[1]] != '#' && temp[red2[0] + dir[d][0]][red2[1]] != 'B') {
						temp[red2[0]][red2[1]] = '.';
						red2[0] += dir[d][0];
						
						if (temp[red2[0]][red2[1]] == 'O') {
							finish[0] = true;
							break;
						}

						temp[red2[0]][red2[1]] = 'R';
					}
				}
				//빨간 구슬이 파란 구슬보다 위쪽에 위치할 경우 빨간 구슬부터 움직여줌
				else {
					while (temp[red2[0] + dir[d][0]][red2[1]] != '#') {
						temp[red2[0]][red2[1]] = '.';
						red2[0] += dir[d][0];
						
						if (temp[red2[0]][red2[1]] == 'O') {
							finish[0] = true;
							break;
						}

						temp[red2[0]][red2[1]] = 'R';
					}
					
					while (temp[blue2[0] + dir[d][0]][blue2[1]] != '#' && temp[blue2[0] + dir[d][0]][blue2[1]] != 'R') {
						temp[blue2[0]][blue2[1]] = '.';
						blue2[0] += dir[d][0];
						
						if (temp[blue2[0]][blue2[1]] == 'O') {
							finish[1] = true;
							break;
						}

						temp[blue2[0]][blue2[1]] = 'B';
					}
				}
			} 
			//좌측으로 기울이는 경우
			else if (d == 1) {
				//빨간 구슬이 파란 구슬보다 좌측에 위치할 경우 빨간 구슬부터 움직여줌
				if (red[1] >= blue[1]) {
					while (temp[blue2[0]][blue2[1] + dir[d][1]] != '#') {
						temp[blue2[0]][blue2[1]] = '.';
						blue2[1] += dir[d][1];
						
						if (temp[blue2[0]][blue2[1]] == 'O') {
							finish[1] = true;
							break;
						}
						
						temp[blue2[0]][blue2[1]] = 'B';
					}

					while (temp[red2[0]][red2[1] + dir[d][1]] != '#' && temp[red2[0]][red2[1] + dir[d][1]] != 'B') {
						temp[red2[0]][red2[1]] = '.';
						red2[1] += dir[d][1];
						
						if (temp[red2[0]][red2[1]] == 'O') {
							finish[0] = true;
							break;
						}

						temp[red2[0]][red2[1]] = 'R';
					}
				} 
				//파란 구슬이 빨간 구슬보다 좌측에 위치할 경우 파란 구슬부터 움직여줌
				else {
					while (temp[red2[0]][red2[1] + dir[d][1]] != '#') {
						temp[red2[0]][red2[1]] = '.';
						red2[1] += dir[d][1];
						
						if (temp[red2[0]][red2[1]] == 'O') {
							finish[0] = true;
							break;
						}

						temp[red2[0]][red2[1]] = 'R';
					}
					
					while (temp[blue2[0]][blue2[1] + dir[d][1]] != '#' && temp[blue2[0]][blue2[1] + dir[d][1]] != 'R') {
						temp[blue2[0]][blue2[1]] = '.';
						blue2[1] += dir[d][1];
						
						if (temp[blue2[0]][blue2[1]] == 'O') {
							finish[1] = true;
							break;
						}

						temp[blue2[0]][blue2[1]] = 'B';
					}
				}
			} 
//아래로 기울이는 경우
			else if (d == 2) {
				//빨간 구슬이 파란 구슬보다 아래쪽에 위치할 경우 빨간 구슬부터 움직여줌
				if (red[0] >= blue[0]) {
					while (temp[red2[0] + dir[d][0]][red2[1]] != '#') {
						temp[red2[0]][red2[1]] = '.';
						red2[0] += dir[d][0];
						
						if (temp[red2[0]][red2[1]] == 'O') {
							finish[0] = true;
							break;
						}

						temp[red2[0]][red2[1]] = 'R';
					}

					while (temp[blue2[0] + dir[d][0]][blue2[1]] != '#' && temp[blue2[0] + dir[d][0]][blue2[1]] != 'R') {
						temp[blue2[0]][blue2[1]] = '.';
						blue2[0] += dir[d][0];
						
						if (temp[blue2[0]][blue2[1]] == 'O') {
							finish[1] = true;
							break;
						}

						temp[blue2[0]][blue2[1]] = 'B';
					}
				}
				//파란 구슬이 빨간구슬보다 아래쪽에 위치할 경우 파란 구슬부터 움직여줌
				else {
					while (temp[blue2[0] + dir[d][0]][blue2[1]] != '#') {
						temp[blue2[0]][blue2[1]] = '.';
						blue2[0] += dir[d][0];
						
						if (temp[blue2[0]][blue2[1]] == 'O') {
							finish[1] = true;
							break;
						}

						temp[blue2[0]][blue2[1]] = 'B';
					}
					
					while (temp[red2[0] + dir[d][0]][red2[1]] != '#' && temp[red2[0] + dir[d][0]][red2[1]] != 'B') {
						temp[red2[0]][red2[1]] = '.';
						red2[0] += dir[d][0];
						
						if (temp[red2[0]][red2[1]] == 'O') {
							finish[0] = true;
							break;
						}

						temp[red2[0]][red2[1]] = 'R';
					}
				}
			} 
			//우측으로 기울이는 경우
			else if (d == 3) {
				//빨간 구슬이 파란 구슬보다 우쪽에 위치할 경우 빨간 구슬부터 움직여줌
				if (red[1] >= blue[1]) {
					while (temp[red2[0]][red2[1] + dir[d][1]] != '#') {
						temp[red2[0]][red2[1]] = '.';
						red2[1] += dir[d][1];
						
						if (temp[red2[0]][red2[1]] == 'O') {
							finish[0] = true;
							break;
						}

						temp[red2[0]][red2[1]] = 'R';
					}

					while (temp[blue2[0]][blue2[1] + dir[d][1]] != '#' && temp[blue2[0]][blue2[1] + dir[d][1]] != 'R') {
						temp[blue2[0]][blue2[1]] = '.';
						blue2[1] += dir[d][1];
						
						if (temp[blue2[0]][blue2[1]] == 'O') {
							finish[1] = true;
							break;
						}

						temp[blue2[0]][blue2[1]] = 'B';
					}
				} 
				//파란 구슬이 빨간 구슬보다 우쪽에 위치할 경우 파란 구슬부터 움직여줌
				else {
					while (temp[blue2[0]][blue2[1] + dir[d][1]] != '#') {
						temp[blue2[0]][blue2[1]] = '.';
						blue2[1] += dir[d][1];
						
						if (temp[blue2[0]][blue2[1]] == 'O') {
							finish[1] = true;
							break;
						}

						temp[blue2[0]][blue2[1]] = 'B';
					}
					
					while (temp[red2[0]][red2[1] + dir[d][1]] != '#' && temp[red2[0]][red2[1] + dir[d][1]] != 'B') {
						temp[red2[0]][red2[1]] = '.';
						red2[1] += dir[d][1];
						
						if (temp[red2[0]][red2[1]] == 'O') {
							finish[0] = true;
							break;
						}

						temp[red2[0]][red2[1]] = 'R';
					}
				}
			}
			
			//파란 구슬이 구멍에 빠진 경우
			if (finish[1]) {
				continue;
			}
			
			//빨간 구슬이 구멍에 빠진 경우(파란 구슬 x)
			if (finish[0]) {
				answer = Math.min(answer, cnt);
				continue;
			}
			
			simulation(d, cnt + 1, temp, red2, blue2);
		}
	}

	public static void copyMap(char[][] map, char[][] temp) {
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < M; ++j) {
				temp[i][j] = map[i][j];
			}
		}
	}
}