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

문제

문제 바로가기> BOJ 1194번: 달이 차오른다, 가자.

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

 

풀이

미로를 탈출하는데 드는 이동 횟수의 최솟값을 찾는 것이므로, BFS

키를 가진 상태(2^6 경우 존재)에서의 방문 여부를 체크해줘야 하므로, 비트마스킹을 이용했다. 

 

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

public class Main {
	
	static final int[] dy = {-1,1,0,0};
	static final int[] dx = {0,0,-1,1};
	
	static int N, M;
	static int sy, sx;
	static char[][] map;
	static boolean[][][] visited;
	
	private static int solution() {
		
		ArrayDeque<int[]> q = new ArrayDeque<>();
		q.offer(new int[] {sy, sx, 0, 0}); // y, x, k, cnt
		visited[sy][sx][0] = true;
		
		while(!q.isEmpty()) {
			int y = q.peek()[0];
			int x = q.peek()[1];
			int k = q.peek()[2];
			int cnt = q.peek()[3];
			q.poll();
			
			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(map[ny][nx] =='#' || visited[ny][nx][k]) continue; // 벽인 경우, 이미 방문한 경우
				
				char c =  map[ny][nx];
				if(c == '1') return cnt+1; // 민식이가 가야하는 곳
				else if(c=='.') { // 빈칸
					q.offer(new int[] {ny, nx, k, cnt+1});
					visited[ny][nx][k] = true;
				}
				else if('a' <= c && c <= 'f') { // 열쇠 획득 (bit masking 설정)
					int nk = k | (1 << (c-'a'));
					q.offer(new int[]{ny, nx, nk, cnt+1});
					visited[ny][nx][nk] = true;
				}
				else if('A' <= c && c <= 'F') { // 문인 경우 (해당하는 키가 있는지 확인)
					if((k & (1 << (c-'A'))) != 0) { // 키가 있는 경우
						q.offer(new int[] {ny, nx, k, cnt+1});
						visited[ny][nx][k] = true;
					}
				}
			}
		}
		return -1;
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		// input
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new char[N][M];
		visited = new boolean[N][M][1<<6]; // 2^6
		
		for(int i=0; i<N; i++) {
			String line = br.readLine();
			for(int j=0; j<M; j++) {
				map[i][j] = line.charAt(j);
				if(map[i][j] == '0') { // 시작점 
					sy = i; sx = j;
					map[i][j] = '.';
				}
			}
		}
		
		// solution
		System.out.println(solution());
	}
}