boj 1194 달이 차오른다, 가자.

www.acmicpc.net/problem/1194

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

기본적인 bfs에 비트마스킹이 더해진 문제입니다.

 

visit[x][y][key] : (x, y)에 도달했을 때 갖고있는 열쇠 종류

문을 열기 위해서는 열쇠를 갖고있어야 하므로 얻은 열쇠를 비트마스킹을 이용하여 관리합니다.

 

로직은 다른 bfs와 똑같이 돌아가며, 확인해야할 조건은

1. 맵 밖으로 나갈 경우

2. 문을 만났을 경우

3. 열쇠를 만났을 경우

4. 해당 좌표를 이미 방문한 경우

5. 벽을 만난 경우

 

1, 4, 5인 경우에는 continue를 해주시면 되고,

2인 경우에는 열쇠가 없는 경우에만 continue를 해주시면 됩니다.

3인 경우에는 열쇠를 추가합니다.

 

탈출에 성공하였으면 현재 시간을 출력해주시고, 큐가 비었는데도 탈출하지 못했으면 -1을 출력합니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static Deque<int[]> dq = new ArrayDeque<>();
    static char list[][] = new char[51][51];
    static boolean visit[][][] = new boolean[51][51][64];
    static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static int N, M;
 
    static void bfs() {
        for (int t = 0; !dq.isEmpty(); t++) {
            int size = dq.size();
            while (size-- > 0) {
                int x = dq.peek()[0];
                int y = dq.peek()[1];
                int key = dq.poll()[2];
 
                if (list[x][y] == '1') {
                    System.out.println(t);
                    return;
                }
                for (int i = 0; i < 4; i++) {
                    int nx = x + direct[i][0];
                    int ny = y + direct[i][1];
                    int nextKey = key;
 
                    if (nx < 0 || ny < 0 || nx >= N || ny >= M)
                        continue;
                    if ('A' <= list[nx][ny] && list[nx][ny] <= 'F') {
                        int door = list[nx][ny] - 'A';
 
                        if ((key & (1 << door)) == 0)
                            continue;
                    }
                    if ('a' <= list[nx][ny] && list[nx][ny] <= 'f') {
                        nextKey = nextKey | (1 << (list[nx][ny] - 'a'));
                    }
 
                    if (visit[nx][ny][nextKey] || list[nx][ny] == '#')
                        continue;
                    dq.add(new int[] { nx, ny, nextKey });
                    visit[nx][ny][nextKey] = true;
                }
            }
        }
        
        System.out.println(-1);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i] = st.nextToken().toCharArray();
            for (int j = 0; j < M; j++) {
                if (list[i][j] == '0') {
                    dq.add(new int[] { i, j, 0 });
                    visit[i][j][0] = true;
                }
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        bfs();
    }
}