백준 - 구슬탈출2(13460)

1. 문제

문제 링크

문제
스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.

보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다.

이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다.

각각의 동작에서 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.

보드의 상태가 주어졌을 때, 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.

입력
첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다.

입력되는 모든 보드의 가장자리에는 모두 '#'이 있다. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.

출력
최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력한다. 만약, 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.

2. 풀이

2-1 조건

1. 빨간 구슬만 구멍에 들어가야한다.
2. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다.
3. 10번 이하로 움직여서 빨간 구슬을 구멍에 통과시키지 못하면 -1을 출력한다.

2-2 계획

이 문제는 최소 몇 번의 기울임으로 빨간 구슬을 빼낼 수 있는지 출력해야하므로
bfs를 이용하여 풀어야 한다는 사실을 알 수 있습니다.

그러면 각 상태 공간은 어떻게 정의할 수 있을까요?
이 문제가 초급 bfs문제보다 한 단계 더 어려운 이유는 상태 공간을 어떻게 정의할 것인가?
이 부분에서 까다로움을 느끼지 않을까 싶습니다.

초급 bfs는 물체 하나에 대해서 이리저리 움직여서 상태를 기록하는 문제가 대부분입니다.
이러한 사고 방식으로 이 문제에 접근하면
빨간 구슬의 상태만 기록하며 문제를 풀게될 수 있습니다.
그러면 우리가 2-1에서 정리한 조건들에 맞게 시뮬레이션을 하고 있는지 체크하기 어렵겠죠?

그러면 상태 공간을 어떻게 정의하면 좋을까요?
상태 공간을 물체를 주제로 바라보지 않고,
어떤 동작을 한 번 수행했을 때 바뀌는 변수들로 생각해보면 어떨까요?

우리는 게임판을 들고 이리저리 기울여보며 빨간 구슬을 빼내야 합니다.
그렇다면 기울이는 동작을 할 때마다 바뀌는 변수들은 무엇일까요?
정답은 빨간 구슬의 좌표, 파란 구슬의 좌표, 기울인 횟수가 있습니다.

우리는 위에서 알아낸 필요한 변수들을 상태 공간으로 정의한 다음,
게임판의 기울임을 구현해서 bfs로 시뮬레이션을 하면 답을 구할 수 있음을 알 수 있습니다.

다시 총 정리를 해보면

• bfs를 통해 게임판을 북동남서로 기울여보며 빨간 구슬과 파란 구슬의 좌표를 이동

  1. 빨간 구슬과 파란 구슬의 좌표가 같다면 기울였던 방향과 이전 구슬들의 좌표를 토대로 현재 좌표 재조정(2번 조건)
  2. 파란 구슬이 구멍에 빠졌다면 그 상태는 기록하지 않음(1번 조건)

• 빨간 구슬의 좌표, 파란 구슬의 좌표를 visit배열에 기록하며 탐색 진행

• 빨간 구슬이 10번 이내로 구멍 통과시 답 출력(3번 조건)

3. 전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static int N, M, my[] = {-1, 0, 1, 0}, mx[] = {0, 1, 0, -1};
	static char[][] m;
	static boolean visit[][][][];
	
	public static void main(String[] args) throws Exception {
		String[] s = br.readLine().split(" ");
		N = Integer.parseInt(s[0]);
		M = Integer.parseInt(s[1]);
		
		m = new char[N][M];
		visit = new boolean[N][M][N][M];
		
		//  초기 구슬 위치 저장 변수 선언
		int ry = 0, rx = 0, by = 0, bx = 0;
		
		for (int i = 0; i < N; i++) {
			String c = br.readLine();
			for (int j = 0; j < M; j++) {
				char d = c.charAt(j);
				
				if (d == 'R') {
					ry = i;
					rx = j;
				} else if (d == 'B') {
					by = i;
					bx = j;
				}
				
				m[i][j] = d;
			}
		}
		
		Queue<int[]> q = new LinkedList<>();
		
		q.add(new int[] {ry, rx, by, bx, 0});
		visit[ry][rx][by][bx] = true;
		
		int ans = -1;
		
		out: while (!q.isEmpty()) {
			int[] cur = q.poll();
			
			// 10번 시도해도 안되는 경우 (3번 조건)
			if (cur[4] > 9) break;
			
			for (int dir = 0; dir < 4; dir++) {
				// 다음 빨간 구슬 좌표와 탈출 여부
				int[] NR = move(cur[0], cur[1], dir);
				// 다음 파란 구슬 좌표와 탈출 여부
				int[] NB = move(cur[2], cur[3], dir);
				
				// 파란 구슬이 탈출시 넘어감(1 - 2번 계획, 1번 조건)
				if (NB[2] == 1) continue;
				
				// 빨간 구슬 탈출시 답
				if (NR[2] == 1) {
					ans = cur[4] + 1;
					break out;
				}
				
				// 같은 칸에 있을 때 방향과 이전 위치에 따라 현위치 재조정 (1 - 1번 계획, 2번 조건)
				if (NR[0] == NB[0] && NR[1] == NB[1]) {
					switch (dir) {
					case 0:
						if (cur[0] < cur[2]) NB[0]++;
						else NR[0]++;
						break;
					case 1: 
						if (cur[1] < cur[3]) NR[1]--;
						else NB[1]--;
						break;
					case 2: 
						if (cur[0] < cur[2]) NR[0]--;
						else NB[0]--;
						break;
					case 3: 
						if (cur[1] < cur[3]) NB[1]++;
						else NR[1]++;
						break;
					}
				}
				
				// 북동남서로 돌릴 때마다 빨간공, 파란공의 위치 정보를 저장한다.
				// 만약 저장했던 위치 정보가 그대로 있을시 탐색하지 않아도 된다는 뜻. (2번 계획)
				if (!visit[NR[0]][NR[1]][NB[0]][NB[1]]) {
					visit[NR[0]][NR[1]][NB[0]][NB[1]] = true;
					q.add(new int[] {NR[0], NR[1], NB[0], NB[1], cur[4] + 1});
				}
			}
			
		}
		
		bw.write(ans + "");
		bw.close();
	}
	
	// 게임판을 기울여서 구슬을 움직이는 함수
	static int[] move(int y, int x, int dir) {
		int retY = y, retX = x, escape = 0, ny = y + my[dir], nx = x + mx[dir];

		while (m[ny][nx] != '#') {
			retY = ny;
			retX = nx;
		
			if (m[ny][nx] == 'O') {
				escape = 1;
				break;
			};
	
			ny += my[dir];
			nx += mx[dir];
		}
		
		return new int[] {retY, retX, escape};
	}
}