아이디어

• BFS를 사용한다.
• 단, 이전에 탐색한 칸이라도 획득한 열쇠들이 다르면 재탐색해야 한다.
  • 열쇠가 있다면 문을 열 수 있기 때문이다.
• 따라서 방문 여부 체크 배열(여기서는 enqueued)는 열쇠 상태과 좌표를 포함한 3차원 boolean 배열이 된다.
• 여기서 열쇠 상태를 비트마스킹을 통해 표현한다.
  • 0~5번 비트가 열쇠 a~f의 획득 여부를 가리키도록 한다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tk = null;

	static int N, M, sy, sx;
	static char[][] map;
	static Queue<Node> q = new ArrayDeque<>();
	static boolean[][][] enqueued;	// [key_flag][y][x]
	
	static int[] dy = {-1, 0, 1, 0};
	static int[] dx = {0, 1, 0, -1};
	
	public static void main(String[] args) throws Exception {
		tk = new StringTokenizer(rd.readLine());
		N = Integer.parseInt(tk.nextToken());
		M = Integer.parseInt(tk.nextToken());
		
		map = new char[N][];
		enqueued = new boolean[1 << 6][N][M];
		
		for (int i=0; i<N; i++) {
			map[i] = rd.readLine().toCharArray();
			for (int j=0; j<M; j++) {
				if (map[i][j] == '0') {
					sy = i;
					sx = j;
				}
			}
		}
		
		q.offer(new Node(0, sy, sx));
		enqueued[0][sy][sx] = true;
		
		int m = 0;
		while (true) {
			int size = q.size();
			if (size == 0) break;
			for (int i=0; i<size; i++) {
				Node node = q.poll();
				int flag = node.flag;
				int y = node.y;
				int x = node.x;
				
				if (map[y][x] == '1') {
					System.out.println(m);
					return;
				}
				if ('a' <= map[y][x] && map[y][x] <= 'f')
					flag |= 1 << (map[y][x] - 'a');
				
				for (int d=0; d<4; d++) {
					int ny = y + dy[d];
					int nx = x + dx[d];
					if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
					if (enqueued[flag][ny][nx]) continue;
					if (map[ny][nx] == '#') continue;
					if ('A' <= map[ny][nx] && map[ny][nx] <= 'F' && (flag & 1 << (map[ny][nx] - 'A')) == 0) continue;
					
					q.offer(new Node(flag, ny, nx));
					enqueued[flag][ny][nx] = true;
				}
			}
			m++;
		}
		
		System.out.println(-1);
	}
	
	static class Node {
		int flag, y, x;
		Node(int flag, int y, int x) {
			this.flag = flag;
			this.y = y;
			this.x = x;
		}
	}
}

메모리 및 시간

• 메모리: 15960 KB
• 시간: 152 ms

리뷰

• 비슷한 문제들을 풀어봐서 쉽게 풀 수 있었던 것 같다.
  • 3차원 방문 배열 - 백준 1600 '말이 되고픈 원숭이'
  • 비트마스크 인덱싱 - 백준 1029 '그림 교환'