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

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

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

풀이

🪑 BFS + 비트마스킹이 결합된 문제이다! 재밌었던 문제였다. 특히 열쇠를 가지고 있는지 여부를 하나씩 계산해 주다가 비트마스킹으로 간편하게 확인할 수 있는 방법을 알게 되고 너무 신세계였다.

 

📝 문제의 조건을 정리해 보자!

• 주어진 미로를 탈출하는데 걸리는 최소 이동 횟수를 구한다.
• 0에서 출발하여 1로 탈출한다
• 문은 대응하는 열쇠를 먼저 얻어야 열 수 있다.
• 같은 타입의 열쇠가 여러개 존재할 수 있다.

 

 

🔧 문제를 풀어보자!

1. 최소 이동 횟수를 구하므로 BFS를 사용한다.
2. 방문체크가 중요하다. 방문체크시 열쇠의 소유 여부를 함께 체크한다.
3. 탐색 중에 열쇠를 만나면 해당 열쇠를 현재 열쇠 정보에 추가해 준다.
4. 탐색 중에 문을 만나면 해당 문에 맞는 열쇠를 가지고 있는지 확인한 후 탐색한다.

 

 

🔹 BFS를 사용한다.

- 최소 이동 횟수 즉, BFS문제이다.

 

🔹 방문체크시 열쇠의 소유 여부를 함께 체크한다.

- 어떻게 소유 여부를 체크해 줄 수 있을지 고민하다가, 리눅스의 권한 관리가 떠올랐다. 권한에 대한 정보를 숫자로 표현하였고, 나도 여기에서 힌트를 얻어 다음과 같이 표현하였다.

• 열쇠 a는 2의 0제곱 -> 1
• 열쇠 b는 2의 1제곱 -> 2
• 열쇠 c는 2의 2제곱 -> 4
• 열쇠 d는 2의 3제곱 -> 8
• 열쇠 e는 2의 4제곱 -> 16
• 열쇠 f는 2의 5제곱 -> 32

모든 열쇠를 다 가지고 있다면 63이된다. 그러므로 방문 체크 할 배열의 크기를 64로 제한해 주었다.

 

🙋‍♀️ 위와 같은 방식으로 하면 문제점이 있다. 문을 만났을때 문에 맞는 열쇠를 가지고 있는지 확인하는 과정이 까다롭다.

그래서 위의 방식을 비트 표현 방식으로 변경해 주었다.

• 열쇠 a -> 000001
• 열쇠 b -> 000010
• 열쇠 c -> 000100
• 열쇠 d -> 001000
• 열쇠 e -> 010000
• 열쇠 f -> 100000

이렇게 표현하면 비트를 숫자로도 표현할 수 있으며 해당 비트가 1인지 0인지 비트연산을 통해 확인하여 열쇠 소유 여부를 빠르게 확인할 수 있다.

 

🔹 탐색 중에 열쇠를 만나면 해당 열쇠를 현재 열쇠 정보에 추가해 준다.

- 열쇠에 종류에 따라 1의 쉬프트 연산을 해준다. 

- 쉬프트 연산을 해 주어 얻은 새로운 열쇠의 정보를 현재 가지고 있는 key값과 OR연산하여 새로운 열쇠 정보를 기존의 key에 더해주고 탐색을 진행하면 된다.

 

🔹 탐색 중에 문을 만나면 해당 문에 맞는 열쇠를 가지고 있는지 확인한 후 탐색한다.

- 해당 열쇠에 해당하는 비트가 1인지만 확인하면 된다.

- 만난 문의 종류에 따라 1의 쉬프트 연산을 해준다.

- 해당 비트의 값과 현재 key값을 AND 연산으로 비교한다. AND연산은 연산하는 두 값의 비트가 모두 1이어야 1을 반환하므로 1인지 확인한다. 

- 이때 결과는 001000등 비트로 확인되므로 이 값을 정수로 변환하여 현재 열고자 하는 문에 해당하는 열쇠 정보가 8인지만 확인해 주면 된다.

 

코드

//1944: 복제 로봇
import java.io.*;
import java.util.*;
 
public class Main {
 
    static int n, m;
    static char[][] board;
    static Node start;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
 
    public static void main(String[] args) throws IOException {
 
        //입력
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 
        String str = bf.readLine();
        StringTokenizer st = new StringTokenizer(str);
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
 
        board = new char[n][m];
        for(int i = 0; i < n; i++) {
            str = bf.readLine();
            for(int j = 0; j < m; j++) {
                char c = str.charAt(j);
                board[i][j] = c;
                if(c == '0') start = new Node(i, j, 0, 0);
            }
        }
        //입력 끝
        System.out.println(bfs());
    }   
 
    public static int bfs() {
        Queue<Node> q = new LinkedList<>();
        boolean[][][] visited = new boolean[n][m][64]; //열쇠 가지고 방문 여부 체크. 
        q.offer(start);
        visited[start.x][start.y][0] = true;
 
        while(!q.isEmpty()) {
            Node current = q.poll();
            if(board[current.x][current.y] == '1') return current.cost;
 
            for(int i = 0; i < 4; i++) {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];
 
                if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                if(visited[nx][ny][current.key] || board[nx][ny] == '#') continue;
                
                if(board[nx][ny] >= 'a' && board[nx][ny] <= 'f') { //열쇠
                    int next_key = 1 << (board[nx][ny] - 'a');
                    next_key = current.key | next_key;
                    visited[nx][ny][next_key] = true;
                    q.offer(new Node(nx, ny, current.cost + 1, next_key));
                }
                else if(board[nx][ny] >= 'A' && board[nx][ny] <= 'F') { //문
                    if((current.key & 1 << (board[nx][ny] - 'A')) == (int)Math.pow(2, board[nx][ny] - 'A')) { //해당 비트가 켜져있는지 확인
                        visited[nx][ny][current.key] = true;
                        q.offer(new Node(nx, ny, current.cost + 1, current.key));
                    }
                } else {
                    visited[nx][ny][current.key] = true;
                    q.offer(new Node(nx, ny, current.cost + 1, current.key));
                }
            }
        }
        return -1;
    }
 
    public static class Node {
        int x, y, cost, key;
 
        public Node(int x, int y, int cost, int key) {
            this.x = x;
            this.y = y;
            this.cost = cost;
            this.key = key;
        }
    }
}