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

문제설명

www.acmicpc.net/problem/1194

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

 

기본아이디어

일단 문제 자체는 최단경로로 도착지점에 도착하는 거리를 구하는 문제이다. BFS 탐색을 쓰면 되겠다는 생각을 가지고 열쇠를 어떻게 처리를 해야하나 고민을 했다.

 

방문처리 방식을 추가하기로 했다. 자세하게 설명하면 BFS탐색을 할 때 한번 지나간 곳은 Boolean 배열로 방문했다는 정보를 남기고 진행을 한다. 이렇게 되면 지나온 곳을 다시 돌아가지도 않고 후에 다른 루트를 통해 해당 지점에 도달해도 이미 방문했던 곳이기 때문에 나아갈 수 없다. BFS는 Queue에서 FIFO 방식으로 진행이 되기 때문에 무조건 앞에 먼저 방문했던 루트가 더 빠를 수 밖에 없기에 최단경로를 구하는 입장에서는 굳이 그보다 느린 루트를 다시 한번 확인할 필요가 없다.

 

하지만 이런 방식에 추가로 열쇠를 획득한 경우 이전에 왔던 곳도 다시 탐색을 할 수 있게 해줘야 한다. 왜냐하면 이전에는 갈 수 없었던 획득한 열쇠로 열 수 있는 문을 통과할 수 있기 때문에 열쇠를 획득한 시점부터 다시 처음부터 도착지점에 갈 수 있는 가능성이 생긴다. 그리고 열쇠가 여러개 존재하기 때문에 열쇠를 가진 경우의 수, 예를 들어 1번, 3번을 가진 경우를 1번을 가진 경우 3번을 가진 경우와 구분해서 생각해야 한다. 그렇기 때문에 현재 가진 열쇠의 종류를 비트 마스킹을 활용하면 integer 하나로 그 정보를 가지고 다닐 수 있다. 이를 이용하면 BFS 탐색에 용이하게 정보를 가지고 다닐 수 있게 된다.

 

구현코드

 public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(input.readLine());
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        map = new char[N][];
        for(int i = 0; i < N; i++){
            map[i] = input.readLine().toCharArray();
        }
        int r = 0;
        int c = 0;
        out:for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                if(map[i][j] == '0'){
                    r = i;
                    c = j;
                    break out;
                }
            }
        }
        visited = new boolean[N][M][(1<<6)];
        min_dist = Integer.MAX_VALUE;
        bfs(r, c);
 
        System.out.println(min_dist==Integer.MAX_VALUE? -1: min_dist);
    }
    static int N, M;
    static int min_dist;
    static char[][] map;
    static boolean[][][] visited;
    static int[] dr = {0, 0, 1, -1};
    static int[] dc = {1, -1, 0, 0};
    static void bfs(int r, int c){
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{r,c,0});
        int dist = 0;
        while (!queue.isEmpty()){
            dist++;
            int q_size = queue.size();
            for(int i = 0; i < q_size; i++){
                int[] now = queue.poll();
                for(int d = 0; d < 4; d++){
                    int nr = now[0] + dr[d];
                    int nc = now[1] + dc[d];
                    if(isIn(nr, nc) && !visited[nr][nc][now[2]]){
                        char next = map[nr][nc];
                        if(next == '.'){
                            visited[nr][nc][now[2]] = true;
                            queue.add(new int[]{nr, nc, now[2]});
                            continue;
                        }else if(next == '#'){
                            continue;
                        }else if(next=='0'){
                            visited[nr][nc][now[2]] = true;
                            queue.add(new int[]{nr, nc, now[2]});
                            continue;
                        }else if(next == '1'){
                            min_dist = dist;
                            return;
                        }else if(next >= 'a' && next <='f'){
                            visited[nr][nc][now[2]] = true;
                            queue.add(new int[]{nr, nc, now[2]|(1<<(next-'a'))});
                            continue;
                        }else if(next >= 'A' && next <= 'F'){
                            if((now[2]>>(next-'A')&1) == 1){
                                visited[nr][nc][now[2]] = true;
                                queue.add(new int[]{nr, nc, now[2]});
                                continue;
                            }
                        }
                    }
                }
            }
        }
    }
    static boolean isIn(int r, int c){
        return r >= 0 && r < N && c >= 0 && c < M;
    }
 

 

정리, 기억할 내용

1. 최단경로 탐색, BFS탐색 기억하자.

2. 비트 마스킹!!

3. 방문처리를 구분해야하는 경우인지 확인!