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

문제 출처: www.acmicpc.net/problem/1194

1194번: 달이 차오른다, 가자.

: 민식이가 0에서 출발하여 1까지 도착할 수 있는지 보고 할 수 있다면 이동 횟수의 최솟값을 구해야 한다.

: 미로의 구성은 빈곳, 벽, 열쇠, 문, 민식이의 위치, 출구가 있다.

: 민식이의 위치는 하나이지만 출구의 위치는 여러개일 수 있기 때문에 ArrayList로 관리한다.

: 민식이는 이웃한 곳으로 움직일 수 있는데 만약 문을 만날 경우 해당하는 문자 열쇠를 가지고 있어야 한다.

: 열쇠를 가지고 있는지 없는지를 관리하기 위해 비트마스킹을 사용한다.

: 열쇠를 하나도 가지고 있지 않은 경우는 1이고 각 문자마다 1씩 증가시켜 시프트연산을 한다.

: 이러한 과정을 거치면 어떤 열쇠를 가지고 해당 지점을 방문했는지를 기록할 수 있고, 같은 지점을 여러번 가지 않을 수 있다.

: bfs 방식으로 각 지점을 거치면서 출구 중 한 곳에 도달하게 되면 즉시 중단하고 그 때까지의 이동횟수를 반환한다.

: 만약 끝까지 시도했지만 출구를 만나지 못하게 돼서 함수의 끝에 도달하면 -1을 반환하여 도착할 수 없음을 표시한다.

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

public class 달이차오른다가자 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static int R, C;
	static char[][] map;
	static boolean[][][] v;
	static class Point{
		int r, c, key, cnt;

		public Point(int r, int c) {
			super();
			this.r = r;
			this.c = c;
			
		}

		public Point(int r, int c, int key) {
			super();
			this.r = r;
			this.c = c;
			this.key = key;
		}

		public Point(int r, int c, int key, int cnt) {
			super();
			this.r = r;
			this.c = c;
			this.key = key;
			this.cnt = cnt;
		}

		@Override
		public String toString() {
			return "Point [r=" + r + ", c=" + c + ", key=" + key + ", cnt=" + cnt + "]";
		}
		
	}
	static Point start;
	static ArrayList<Point> dest = new ArrayList<>();
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		
		map = new char[R][C];
		v = new boolean[R][C][1<<7];
		for(int i = 0; i < R; i++) {
			String str = br.readLine();
			for(int j = 0; j < C; j++) {
				map[i][j] = str.charAt(j);
				if(map[i][j] == '0') start=new Point(i, j);
				else if(map[i][j] == '1') dest.add(new Point(i, j));
			}
		}
		
		int res = bfs();
		System.out.println(res);
	}
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
	private static int bfs() {
		Queue<Point> q = new LinkedList<>();
		q.offer(new Point(start.r, start.c, 1, 0));
		v[start.r][start.c][1] = true;
		
		while(!q.isEmpty()) {
			Point cur = q.poll();
			for(int i = 0; i < 4; i++) {
				int nr = cur.r + dr[i];
				int nc = cur.c + dc[i];
				
				// 도착지에 오면
				for(int j = 0, size = dest.size(); j < size; j++ ) {
					if(nr == dest.get(j).r && nc == dest.get(j).c) {
						return cur.cnt+1;
					}					
				}
				if(nr < 0 || nr >= R || nc < 0 || nc >= C || map[nr][nc] == '#' || v[nr][nc][cur.key]) continue;
				
				int key = 1;
				// 키를 만나면
				if(map[nr][nc] >= 'a' && map[nr][nc] <= 'f') {
					key = 1 << (map[nr][nc]-'a'+1);
				}
				
				// 문에 만났을 경우
				if(map[nr][nc] >= 'A' && map[nr][nc] <= 'F') {
					//해당 키가 있는지 판단
					if((cur.key & (1 << (map[nr][nc]-'A'+1))) != 1<<(map[nr][nc]-'A'+1)) // 해당 키가 없으면 다음 차례 탐색
						continue;		
				}
				// 그냥 길인 경우(.) 포함
				v[nr][nc][cur.key] = true;
				q.offer(new Point(nr, nc, cur.key | key, cur.cnt+1));
			}
			
		}
		// 도착 못하면
		return -1;
	}
}