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

[문제]

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

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

 

 

[풀이]

민식이의 최소 이동 횟수를 구해야 하기 때문에 BFS 문제라고 유추할 수 있다.

하지만 일반 BFS 문제와는 다른 점이 크게 두 가지 있는데

1. 열쇠 정보값에 따라 방문할 수 있는 미로가 다르기 때문에 획득하는 열쇠 값을 저장해야 한다.

2. 다른 BFS 문제와는 달리 이미 방문했던 곳을 다시 방문해야 되는 경우가 발생한다.

 

📌 열쇠 정보 저장하기

열쇠 값인 a부터 f 까지의 원소를 갖고 있는지 판단하기 위해 비트마스크를 이용해 열쇠 정보를 저장할 수 있다.

- 열쇠 a → 000001 : 1

- 열쇠 b → 000010 : 2

- 열쇠 c → 000100 : 4

- 열쇠 d → 001000 : 8

- 열쇠 e → 010000 : 16

- 열쇠 f → 100000 : 32

 

열쇠를 획득마다 현재 열쇠 정보와 획득한 열쇠 정보를 OR 연산하면, 획득한 열쇠 정보를 포함한 새 열쇠정보를 얻을 수 있다.

 

획득한 열쇠의 경우의 수는 000000 부터 111111 까지 총 64개의 경우의 수가 발생한다.

 

📌 문 열 수 있는지 확인하기

문 정보도 열쇠와 같이 비트로 표현할 수 있다.

문과 열쇠를 AND 연산한 값이 0이 아니면 해당 문을 열 수 있다는 뜻이 된다.

 

📌 방문 기록

보통의 탐색 문제는 2차원 visited 배열을 통해 방문 기록을 저장하고, 이미 방문한 곳은 다시 방문하지 않았다.

하지만 이 문제는 열쇠를 획득하면, 다시 왔던 길로 되돌아가서 탐색을 할 수 있어야 한다.

따라서 각 열쇠 획득마다 방문 정보를 처음부터 다시 시작해야 하기 때문에 visited 배열을 3차원 배열인 visited[N][M][64]로 선언해 주었다.

만약 획득한 열쇠가 {f} 인 경우 visited[row][col][16]에 방문 여부를 체크하고, 획득한 열쇠가 {a, b, c} 인 경우

visited[row][col][7] 에 방문 여부를 체크하는 것이다.

 

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int N, M;
    static char[][] maze;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    static class Point {
        int x, y, cost, key;

        public Point(int x, int y, int cost, int key) {
            this.x = x;
            this.y = y;
            this.cost = cost;
            this.key = key;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        maze = new char[N][M];

        int start_x = 0, start_y = 0;
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < M; j++) {
                maze[i][j] = str.charAt(j);
                if (maze[i][j] == '0') {
                    start_x = i;
                    start_y = j;
                }
            }
        }
        System.out.println(bfs(start_x, start_y));
    }

    private static int bfs(int start_x, int start_y) {
        Queue<Point> queue = new LinkedList();
        boolean[][][] visited = new boolean[N][M][64];
        queue.offer(new Point(start_x, start_y, 0, 0));
        visited[start_x][start_y][0] = true;

        while (!queue.isEmpty()) {
            Point now = queue.poll();
            if (maze[now.x][now.y] == '1') return now.cost;

            for (int i = 0; i < 4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                if (nx < 0 || ny < 0 || nx >= N || ny >= M
                    || visited[nx][ny][now.key] || maze[nx][ny] == '#') continue;

                char next = maze[nx][ny];
                if (next >= 'a' && next <= 'f') {
                    int next_key = now.key | (1 << (next - 'a'));
                    visited[nx][ny][next_key] = true;
                    queue.offer(new Point(nx, ny, now.cost + 1, next_key));
                } else if (next >= 'A' && next <= 'F') {
                    if ((now.key & (1 << (next - 'A'))) != 0) {
                        visited[nx][ny][now.key] = true;
                        queue.offer(new Point(nx, ny, now.cost + 1, now.key));
                    }
                } else {
                    visited[nx][ny][now.key] = true;
                    queue.offer(new Point(nx, ny, now.cost + 1, now.key));
                }
            }
        }
        return -1;
    }
}