[JAVA] 백준 1194 달이 차오른다 가자

문제

지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다.

민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되어버렸다. 결국 민식이는 모두 잠든 새벽 네시 반쯤 홀로 일어나, 창 밖에 떠있는 달을 보았다.

하루밖에 남지 않았다. 달은 내일이면 다 차오른다. 이번이 마지막기회다. 이걸 놓치면 영영 못간다.

영식이는 민식이가 오늘도 여태것처럼 그냥 잠 들어버려서 못 갈지도 모른다고 생각했다. 하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다.

민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되어져있다.

빈 칸: 언제나 이동할 수 있다. ('.')
벽: 절대 이동할 수 없다. ('#')
열쇠: 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. ('a', 'b', 'c', 'd', 'e', 'f')
문: 대응하는 열쇠가 있을 때만 이동할 수 있다. ('A', 'B', 'C', 'D', 'E', 'F')
민식이의 현재 위치: 빈 곳이고, 민식이가 현재 서 있는 곳이다. ('0')
출구: 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. ('1')
달이 차오르는 기회를 놓치지 않기 위해서, 미로를 탈출하려고 한다. 한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다.

민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 문에 대응하는 열쇠가 없을 수도 있다. '0'은 한 개, '1'은 적어도 한 개 있다. 열쇠는 여러 번 사용할 수 있다.

출력

첫째 줄에 민식이가 미로를 탈출하는데 드는 이동 횟수의 최솟값을 출력한다. 만약 민식이가 미로를 탈출 할 수 없으면, -1을 출력한다.

풀이: bfs, 비트 마스킹

1. 키가 A~F 6개 이므로 키 획득 상태는 총 64개가 가능하다.
2. 키 획득 상태마다 visited 배열을 별도로 구현한다.
3. 키 획득 상태인 0~63의 정수와 x, y좌표를 queue에 넣고 탐색한다.

코드

package baekjoon.gold.g1;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class p1194달이차오른다가자 {
	static int[] dx = new int[] { 0, 0, 1, -1 };
	static int[] dy = new int[] { 1, -1, 0, 0 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int height = Integer.parseInt(st.nextToken());
		int width = Integer.parseInt(st.nextToken());
		char[][] grid = new char[height][width];
		int posI = -1;
		int posJ = -1;
		for (int i = 0; i < height; i++) {
			String input = br.readLine();
			for (int j = 0; j < width; j++) {
				if (input.charAt(j) == '0') {
					posI = i;
					posJ = j;
					grid[i][j] = '.';
				} else {
					grid[i][j] = input.charAt(j);
				}
			}
		}
		boolean[][][] visited = new boolean[64][height][width];
		Queue<int[]> queue = new LinkedList<int[]>();
		queue.offer(new int[] { 0, posI, posJ, 0 }); // 열쇠상태, 높이, 너비, 이동횟수
		visited[0][posI][posJ] = true;
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			for (int i = 0; i < 4; i++) {
				int ni = cur[1] + dy[i];
				int nj = cur[2] + dx[i];
				if (0 <= ni && ni < height && 0 <= nj && nj < width && !visited[cur[0]][ni][nj]) {
					if (grid[ni][nj] == '.') {
						visited[cur[0]][ni][nj] = true;
						queue.offer(new int[] { cur[0], ni, nj, cur[3] + 1 });
					} else if (97 <= grid[ni][nj] && grid[ni][nj] <= 102) {// 키획득
						visited[cur[0]][ni][nj] = true;
						if (((int) Math.pow(2, grid[ni][nj] - 97) & cur[0]) == (int) Math.pow(2, grid[ni][nj] - 97)) {//중복 갱신 방지
							queue.offer(new int[] { cur[0], ni, nj, cur[3] + 1 });
						}else { // 키획득 갱신
							queue.offer(new int[] { cur[0] + (int) Math.pow(2, grid[ni][nj] - 97), ni, nj, cur[3] + 1 });
						}
					} else if (65 <= grid[ni][nj] && grid[ni][nj] <= 70) {// 문
						if (((int) Math.pow(2, grid[ni][nj] - 65) & cur[0]) == (int) Math.pow(2, grid[ni][nj] - 65)) {
							visited[cur[0]][ni][nj] = true;
							queue.offer(new int[] { cur[0], ni, nj, cur[3] + 1 });
						}
					} else if (grid[ni][nj] == '1') {
						System.out.println(cur[3] + 1);
						return;
					}
				}
			}
		}
		System.out.println(-1);
	}
}