[Java] 백준 1194번: 달이 차오른다, 가자.

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

public class BOJ_1194_달이_차오른다_가자 {
	static class Node {
		int r;
		int c;
		int cnt;
		int key;
		
		public Node(int r, int c, int cnt, int key) {
			this.r = r;
			this.c = c;
			this.cnt = cnt;
			this.key = key;
		}
	}
	static int N, M;
	static int[] drc = {0,-1,0,1,0};
	static char[][] MAP;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		MAP = new char[N][M];
		int[] start = new int[2];
		
		for(int i=0; i<N; ++i) {
			String str = br.readLine();
			for(int j=0; j<M; ++j) {
				char ch = str.charAt(j);
				MAP[i][j] = ch;
				
				if(ch == '0') {
					start[0] = i;
					start[1] = j;
				}
			}
		}
		
		System.out.println(bfs(start[0], start[1]));
	}
	private static int bfs(int r, int c) {
		Queue<Node> queue = new LinkedList<>();
		boolean[][][] v = new boolean[N][M][64];
		queue.offer(new Node(r, c, 0, 0));
		v[r][c][0] = true;
		
		while(!queue.isEmpty()) {
			Node poll = queue.poll();
			
			if(MAP[poll.r][poll.c] == '1') {
				return poll.cnt;
			}
			
			for(int d=0; d<4; ++d) {
				int nr = poll.r + drc[d];
				int nc = poll.c + drc[d+1];

				if(nr<0 || nr>=N || nc<0 || nc>=M || MAP[nr][nc] == '#' || v[nr][nc][poll.key]) continue;

				if(MAP[nr][nc] >= 'A' && MAP[nr][nc] <= 'F' && (poll.key & (1<<MAP[nr][nc] - 'A')) == 0) {
					continue;
				} else if(MAP[nr][nc] >= 'a' && MAP[nr][nc] <= 'f') {
					int key = poll.key | (1<<MAP[nr][nc]-'a');
					queue.offer(new Node(nr, nc, poll.cnt+1, key));
					v[nr][nc][key] = true;
				} else {
					v[nr][nc][poll.key] = true;
					queue.offer(new Node(nr, nc, poll.cnt+1, poll.key));					
				}
			}
		}
		
		return -1;
	}

}