달이 차오른다, 가자.

문제

풀이 (비트마스킹)

기존 BFS 문제에서는 2차원 배열로 해결하였다.
하지만 이 문제에서는 2차원 배열로 해결할 수 없었다.

그 이유는 열쇠가 6개 존재하고, 열쇠 상황에 맞게 방문처리를 해야 한다.
처음 열쇠가 없는 상태에서 BFS 탐색하다가 열쇠를 만나면 열쇠가 추가된 상황에서 다시 BFS 탐색을 해야 한다.
그렇기 때문에 3차원 방문처리해야할 배열이 필요한 것이다.

문제에서 열쇠는 최대 6개라 하였고 가능한 모든 경우의 수는
=> 000000 ~ 111111 (64개)가 된다.
따라서 3차원 방문 배열은 Visited[65][N][M] 으로 해야 한다.

만약 BFS 탐색을 하다가 열쇠 (a,b,c,d,e,f)를 먹게 되면 |(비트 연산)으로 열쇠 상황을 업데이트 해준다.

또한 (A, B, C, D, E, F)를 만나게 되면 현재 열쇠 상황을 확인하기 위해 &(비트 연산)으로 현재 문 열쇠가 있는지 확인한다.
여기서 열쇠가 있다면 1, 없다면 0이 될 것이다.

이렇게 탐색하다가 1을 만나면 그 때가 가장 최소거리가 되므로 종료해준다.

코드

import java.io.*;
import java.util.*;

public class Main {
	static int N, M;
	static char[][] graph;
	static boolean[][][] visited;
	static int startRow, startCol;
	static int[][] direction = {
			{1, 0},
			{-1, 0},
			{0, 1},
			{0, -1}
	};
	
	public static void main(String[] args) throws IOException {
	//	BufferedReader br = new BufferedReader(new FileReader("./input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		graph = new char[N][M];
		
		for (int row = 0; row < N; row++) {
			String[] colList = br.readLine().split("");
			
			for (int col = 0; col < M; col++) {
				graph[row][col] = colList[col].charAt(0);
				
				if (graph[row][col] == '0') {
					startRow = row;
					startCol = col;
				}
			}
		}
		
		visited = new boolean[65][N][M];
		Deque<int[]> deque = new LinkedList<>();
		visited[0][startRow][startCol] = true;
		deque.add(new int[] {startRow, startCol, 0, 0}); // row, col, 비트마스킹, cnt
		boolean flg = false;
		
		while (!deque.isEmpty()) {
			int[] cur_arr = deque.pollFirst();
			int cur_row = cur_arr[0];
			int cur_col = cur_arr[1];
			int cur_bit = cur_arr[2];
			int cur_cnt = cur_arr[3];
			
			if (graph[cur_row][cur_col] == '1') {
				System.out.println(cur_cnt);
				flg = true;
				break;
			}
			
			for (int[] direct : direction) {
				int new_row = cur_row + direct[0];
				int new_col = cur_col + direct[1];
				int new_bit = cur_bit;
				
				// 맵 밖으로 나갈 경우
				if (new_row < 0 || new_row == N || new_col < 0 || new_col == M) continue;
				
				// 벽일 경우
				int item = graph[new_row][new_col];
				if (item == '#') continue;
				
				// 방문처리
				if (visited[new_bit][new_row][new_col]) continue;
				
				// 문일 경우
				if (item >= 65 && item <= 70) {
					int check = new_bit & (1 << (item - 65));
					
					if (check == 0) continue;
				}
				
				// 열쇠일 경우
				if (item >= 97 && item <= 102) {
					new_bit |= (1 << (item - 97));
				}
				
				visited[new_bit][new_row][new_col] = true;
				deque.add(new int[] {new_row, new_col, new_bit, cur_cnt + 1});
			}
		}
		
		if (!flg) System.out.println(-1);
	}
	
}