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

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

https://www.acmicpc.net/problem/1194

이 문제를 풀기위해 생각해야 하는 것은 크게 2가지가 있습니다.

1. 획득하는 열쇠 정보를 어떻게 update하고, 문을 만날때마다 어떻게 확인할 것인가??

2. 다른 탐색문제들과는 달리 이미 지나온 길을 다시 되돌아가야하는 경우가 발생합니다.

[열쇠정보 저장하기]

a부터 f까지의 열쇠는 A부터 F까지의 문을 열 수 있습니다.

열쇠를 획득할 때마다 획득한 열쇠정보를 저장할 수 있어야합니다. 열쇠정보를 저장하는 방법은 "비트 마스크"로 

표현하는 방법이 있습니다. 

각각의 열쇠를 비트와 십진수로 표현하면 아래와 같습니다.

열쇠	비트 표현	십진수
a	0 0 0 0 0 1	1
b	0 0 0 0 1 0	2
c	0 0 0 1 0 0	4
d	0 0 1 0 0 0	8
e	0 1 0 0 0 0	16
f	1 0 0 0 0 0	32

위 정보를 가지고 열쇠를 획득할때 마다, 현재 열쇠 정보와 획득한 열쇠 정보를 OR연산을 해주게되면, 

획득한 열쇠정보를 포함한 열쇠정보를 얻을 수 있습니다. 

예를 들어, 열쇠가 전혀없는 초기상태(값 : 0)에서 a라는 열쇠를 획득했다고 가정해봅니다. 

현재 열쇠	획득한 열쇠	현재 OR 획득 열쇠
0 0 0 0 0 0 (없음)	0 0 0 0 0 1 (a)	0 0 0 0 0 1 (a)

위 상태에서 b라는 열쇠를 획득했다고 가정해봅니다.

현재 열쇠	획득한 열쇠	현재 OR 획득 열쇠
0 0 0 0 0 1 (a)	0 0 0 0 1 0 (b)	0 0 0 0 1 1 (a, b)

위 상태에서 다시 f라는 열쇠를 획득했다고 가정해봅니다.

현재 열쇠	획득한 열쇠	현재 OR 획득 열쇠
0 0 0 0 1 1 (a, b)	1 0 0 0 1 0 (f)	1 0 0 0 1 1 (a, b, f)

이처럼 각각의 열쇠를 비트와 OR 연산을 통해 표시할 수 있습니다.

즉, 획득한 열쇠의 경우의 수는 0 0 0 0 0 0 부터 1 1 1 1 1 1 까지 총 64개의 경우의 수가

발생할 수 있습니다.

[문을 열수있는지 확인하기]

열쇠정보를 비트로 표현할 수 있다면 문도 똑같은 방법으로 비트로 표현할 수 있습니다.

획득한 열쇠가 a이고 탐색도중 A라는 문을 만났다고 가정해봅시다.

문	획득한 열쇠	열쇠 AND 문
0 0 0 0 0 1 (A)	0 0 0 0 0 1 (a)	0 0 0 0 0 1 (1)

문과 열쇠를 AND연산하게 되면 값은 1이 나오게 됩니다. 즉, A문에 해당하는 열쇠인 a를 획득했다는 뜻이므로

문을 열 수 있습니다.

획득한 열쇠가 a, b이고 탐색도중 B라는 문을 만났다고 가정해봅시다.

문	획득한 열쇠	열쇠 AND 문
0 0 0 0 1 0  (B)	0 0 0 0 1 1 (a, b)	0 0 0 0 1 0 (2)

문과 열쇠를 AND연산하게 되면 값은 2가 나오게 됩니다. 즉, B문에 해당하는 열쇠인 b를 획득했다는 뜻이므로

문을 열 수 있습니다.

정리하면, 문과 열쇠를 AND연산한 값이 0보다 크게되면 해당 문을 열 수 있다는 뜻이므로 탐색을 계속해서

진행하면 됩니다.

[방문기록 중복 피하기]

이전에 포스팅했던 BFS문제들은 2차원 visited 배열을 통해 방문기록을 저장했습니다.

visited[row][col] == true이면 이미 방문한 지점이므로 다시 방문하지 않으면서 다른 방향으로 탐색을 했습니다.

하지만, 이 문제에서는 하나의 경로를 통해 열쇠를 획득한 뒤, 다시 왔던 길을 통해 탐색을 진행할 수 있어야 합니

다.

그림을 통해 확인해보겠습니다.

위 그림을 보면 하늘색은 열쇠를 찾으러 가는 경로이며, 초록색은 되돌아가야만 하는 경로입니다.

만약 2차원 visited배열만을 사용했다면 열쇠를 찾으러가는 과정에서 원으로 표시된 부분의 visited 배열의 값이

이미 true 이므로 되돌아갈 수 없는 상황이 발생합니다. 

그렇기때문에, 어느 한 열쇠를 획득했다면 다시 처음부터 방문을 시작해야 합니다.

여기서 중요한 것은 2차원 visted배열을 모두 false로 초기화시키는 것이 아닌 각각의 어느 한 열쇠를 획득했을

경우에 대한 방문기록을 따로 가져야 합니다.

그 방법으로는 visited배열을 2차원이 아닌 3차원 배열 visited[64][N][M] 으로 선언해야 합니다.

현재 열쇠의 값에 따라 방문 체크기록을 해줘야 하는 위치는 다음과 같습니다.

현재 열쇠	방문 체크 위치	설명
없음	visited[0][row][col]	획득한 열쇠가 없는 경우
a	visited[1][row][col]	획득한 열쇠가 a인 경우
b	visited[2][row][col]	획득한 열쇠가 b인 경우
c	visited[4][row][col]	획득한 열쇠가 c인 경우
d	visited[8][row][col]	획득한 열쇠가 d인 경우
a, b	visited[3][row][col]	획득한 열쇠가 a, b인 경우
a, b, c	visited[7][row][col]	획득한 열쇠가 a, b, c인 경우

따라서 어느 한 열쇠를 획득할 때마다 현재 열쇠 정보를 갱신하고, 그 열쇠의 값을 참조하여 visited배열에

방문 기록을 해야합니다.

[코드 분석]

1. Queue를 이용한 BFS 탐색을 하면서 해당 칸이 확인합니다.

2. 해당 칸이 '.' 이거나 '0', '1'이라면 그 위치를 탐색합니다.

3. 해당 칸이 열쇠라면 현재 가지고 있는 열쇠정보와 새로 획득한 열쇠의 OR 연산을 통해 열쇠 정보를 갱신합니다.

4. 해당 칸이 문이라면 현재 가지고 있는 열쇠정보와 문의 AND 연산이 1이상이라면 문을 열 수 있다는 뜻이므로

해당 칸의 탐색을 계속해서 진행합니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static int[] dirX = new int[] { 0, 0, -1, 1 };
    public static int[] dirY = new int[] { 1, -1, 0, 0 };
    public static char[][] map;
    public static boolean[][][] visited;
    public static Node start;
    public static int N, M, ans = Integer.MAX_VALUE;
 
    public static void main(String[] args) throws Exception {
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new char[N][M];
        visited = new boolean[64][N][M];
 
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = str.charAt(j);
                if (map[i][j] == '0')
                    start = new Node(i, j, 0, 0);
            }
        }
        System.out.println(bfs());
    }
 
    public static int bfs() {
 
        Queue<Node> q = new LinkedList<Node>();
        q.offer(new Node(start.row, start.col, 0, 0));
        visited[0][start.row][start.col] = true;
 
        while (!q.isEmpty()) {
 
            Node node = q.poll();
            int row = node.row;
            int col = node.col;
            int cnt = node.cnt;
            int key = node.key;
 
            if (map[row][col] == '1') {
                return cnt;
            }
 
            for (int i = 0; i < 4; i++) {
 
                int nr = row + dirX[i];
                int nc = col + dirY[i];
 
                if (isBoundary(nr, nc) && map[nr][nc] != '#' && !visited[key][nr][nc]) {
                    if (map[nr][nc] == '.' || map[nr][nc] == '0' || map[nr][nc] == '1') {
                        visited[key][nr][nc] = true;
                        q.offer(new Node(nr, nc, cnt + 1, key));
 
                    } else if (map[nr][nc] >= 'a' && map[nr][nc] <= 'z') {
                        int newKey = 1 << (map[nr][nc] - 'a');
                        newKey = newKey | key;
                        if (!visited[newKey][nr][nc]) {
                            visited[key][nr][nc] = true;
                            visited[newKey][nr][nc] = true;
                            q.offer(new Node(nr, nc, cnt + 1, newKey));
                        }
 
                    } else if (map[nr][nc] >= 'A' && map[nr][nc] <= 'Z') {
 
                        int door = 1 << (map[nr][nc] - 'A');
                        if ((key & door) > 0) {
                            visited[key][nr][nc] = true;
                            q.offer(new Node(nr, nc, cnt + 1, key));
                        }
                    }
                }
            }
 
        }
        return -1;
    }
 
    public static boolean isBoundary(int row, int col) {
        return (row >= 0 && row < N) && (col >= 0 && col < M);
    }
 
}
 
class Node {
 
    int row;
    int col;
    int cnt;
    int key;
 
    public Node(int row, int col, int cnt, int key) {
        this.row = row;
        this.col = col;
        this.cnt = cnt;
        this.key = key;
    }
 
}