[백준] 달이 차오른다, 가자. (1194) Java

문제 링크

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

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

 

문제 요약

(대충 "장기하와 얼굴들 - 달이 차오른다, 가자" 가사를 이용해서 만든 도입부)

민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되어져있다.

• 빈 칸: 언제나 이동할 수 있다. ('.')
• 벽: 절대 이동할 수 없다. ('#')
• 열쇠: 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. ('a', 'b', 'c', 'd', 'e', 'f')
• 문: 대응하는 열쇠가 있을 때만 이동할 수 있다. ('A', 'B', 'C', 'D', 'E', 'F')
• 민식이의 현재 위치: 빈 곳이고, 민식이가 현재 서 있는 곳이다. ('0')
• 출구: 이 곳에 오면 미로를 탈출한다. ('1')

민식이는 미로를 탈출하려고 한다. 한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다.

민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 문에 대응하는 열쇠가 없을 수도 있다. '0'은 한 개, '1'은 적어도 한 개 있다. 열쇠는 여러 번 사용할 수 있다.

 

출력

첫째 줄에 민식이가 미로를 탈출하는데 드는 이동 횟수의 최솟값을 출력한다. 만약 민식이가 미로를 탈출 할 수 없으면, -1을 출력한다.

 

접근법

일반적인 BFS 문제 같지만, "열쇠"와 "문"이라는 개념이 더해져있다. 열쇠가 없으면 문을 통과할 수 없다는 것.

 

따라서 열쇠를 얻기 전과, 열쇠를 얻은 후가 서로 다른 상태라는 것에서 문제 풀이를 시작하면 된다.

일반적인 방식으로 BFS를 하는데, 열쇠 'a'를 들지 않은 채로 특정 타일을 방문하는 것과, 열쇠 'a'를 든 채로 특정 타일을 방문하는 것은 서로 다른 경우라는 것이다. 물론 소유한 열쇠의 종류에 따라서도 달라진다.

 

즉 BFS를 하면서 queue에 다음 이동 지점을 넣어줄 때, 소유한 열쇠 상태에 대한 정보도 같이 포함시켜서 넣어준다.

그리고 방문 체크를 할 때도, 이미 방문했지만 열쇠 소유 상태가 달라져 있다면 방문하지 않은 것으로 본다.

 

이를 구현하기 위해서 bitmask를 사용했다.

열쇠가 'a', 'b', 'c', 'd', 'e', 'f' 총 6개이므로 길이 6의 bitmask를 사용하여 열쇠 소유 상태를 표현한다.

그리고 visit 배열도 2차원 배열이 아닌, 열쇠 소유 상태까지 포함시키기 위해 visit[rows][cols][2 ^ 6]의 3차원 배열로 만들어준다.

 

2^6인 이유는 6개의 열쇠를 소유할 경우의 수가 2^6 = 64 개 이기 때문이다.

 

즉 이 문제를 다시 해석해보면,

미로를 BFS로 완전탐색 하는데, 열쇠 소유 여부를 따져가며 완전 탐색을 하는 것이다.

사실상 visit이 3차원 배열이 되고, 문을 지날 때 열쇠 소유 여부를 체크해주는 것 말고는 일반적인 BFS와 다를 것이 없다.

출구인 '1'에 도착할 때마다 최소 이동 횟수를 갱신해주는 정도...?

 

코드를 보면 이해가 쉬울 것이다.

 

 

시간 복잡도

O(N * M * 2^6). 최소 이동 횟수를 구해야하므로 BFS를 활용한 완전 탐색을 할 수밖에 없다.

 

 

공간 복잡도

BFS를 하는데 필요한 queue와 map, 3차원 visit 배열 정도.

N과 M이 50 이하이기 때문에 메모리는 딱히 고려할 필요 없다.

 

 

풀면서 놓쳤던 점

BFS에 bitmask를 적용할 수 있다는 사실을 전혀 몰랐다.

매우 창의적이면서도 단순하고 아름다운 문제풀이 방법 같다.

 

 

이 문제에서 얻어갈 점

BFS와 bitmask의 조화

 

 

코드

import java.io.*;
import java.util.*;

public class Main
{
    static int rows, cols;
    static char[][] map;
    static boolean[][][] visit;
    static Point startPoint;

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException
    {
        readRowsCols();

        map = new char[rows][cols];
        readMap();

        System.out.println(Bfs2EscapeMaze());
    }

    static int Bfs2EscapeMaze()
    {
        int minMoveCnt = Integer.MAX_VALUE;
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; //4방향으로 이동

        //3차원 visit 배열. 2^6 = 64. 열쇠 소유 상태의 경우의 수는 64개.
        visit = new boolean[rows][cols][64];

        //bfs에 쓸 queue. 출발 지점을 넣어주면서 초기화.
        Queue<MoveStat> moveStatQueue = new LinkedList<>();
        moveStatQueue.add(new MoveStat(startPoint, 0, 0));

        MoveStat moveStat;
        int tempMinMoveCnt;
        int nextKeyBitmask;

        //BFS 시작.
        while (!moveStatQueue.isEmpty())
        {
            moveStat = moveStatQueue.poll();

            //출구 '1'에 도착했으면 최소 이동 횟수 갱신.
            tempMinMoveCnt = checkCurrentMoveStat(moveStat);
            if (tempMinMoveCnt > 0)
            {
                minMoveCnt = Math.min(minMoveCnt, tempMinMoveCnt);
                continue;
            }

            //4 방향으로 움직여봄.
            for (int[] dir: dirs)
            {
                Point nextPoint = getNextPoint(moveStat.point, dir);

                //다음 지점이 맵 안에 있는지, 벽이 아닌지 확인.
                if (!validatePoint(nextPoint))
                    continue;

                //다음 지점이 열쇠인 경우
                if (isKey(nextPoint))
                {
                    //열쇠를 획득하는 경우이므로 새로운 bitmask 만들어줌
                    nextKeyBitmask =  generateKeyBitmask(moveStat.keyBitmask, map[nextPoint.row][nextPoint.col]);
                    //방문 체크후 방문 안했으면 queue에 넣어줌.. 새로운 bitmask로 체크해주는 것에 유의.
                    if (!visit[nextPoint.row][nextPoint.col][nextKeyBitmask])
                    {
                        visit[nextPoint.row][nextPoint.col][nextKeyBitmask] = true;
                        moveStatQueue.add(new MoveStat(nextPoint, moveStat.moveCnt + 1, nextKeyBitmask));
                    }
                    continue;
                }

                //다음 지점이 문인데, 현재 소유한 열쇠로 열 수 없으면 패스.
                if (isDoor(nextPoint) &&
                        !canOpenDoor(moveStat.keyBitmask, map[nextPoint.row][nextPoint.col]))
                    continue;

                //다음 지점이 빈 공간인데 이미 방문했으면 패스.
                if (visit[nextPoint.row][nextPoint.col][moveStat.keyBitmask])
                    continue;

                //queue에 넣어줌.
                visit[nextPoint.row][nextPoint.col][moveStat.keyBitmask] = true;
                moveStatQueue.add(new MoveStat(nextPoint, moveStat.moveCnt + 1, moveStat.keyBitmask));
            }
        }

        //출구 '1'에 한번도 도착하지 못한 경우.
        if (minMoveCnt == Integer.MAX_VALUE)
            return -1;

        return minMoveCnt;
    }

    static int checkCurrentMoveStat(MoveStat moveStat)
    {
        Point curPoint = moveStat.point;

        if (map[curPoint.row][curPoint.col] == '1')
            return moveStat.moveCnt;

        return 0;
    }

    static int generateKeyBitmask(int bitmask, char key)
    {
        return bitmask | (1 << (key - 'a'));
    }

    static boolean isKey(Point p)
    {
        return map[p.row][p.col] >= 'a' && map[p.row][p.col] <= 'f';
    }

    static boolean isDoor(Point p)
    {
        return map[p.row][p.col] >= 'A' && map[p.row][p.col] <= 'F';
    }

    static boolean canOpenDoor(int keyBitmask, char door)
    {
        return (keyBitmask & (1 << (door - 'A'))) != 0;
    }

    static boolean validatePoint(Point p)
    {
        return p.row >= 0 && p.row < rows && p.col >= 0 && p.col < cols && map[p.row][p.col] != '#';
    }

    static Point getNextPoint(Point curPoint, int[] dir)
    {
        return new Point(curPoint.row + dir[0], curPoint.col + dir[1]);
    }

    static void readRowsCols() throws IOException
    {
        StringTokenizer st = new StringTokenizer(br.readLine());
        rows = Integer.parseInt(st.nextToken());
        cols = Integer.parseInt(st.nextToken());
    }

    static void readMap() throws IOException
    {
        String line;
        for (int row = 0; row < rows; row++)
        {
            line = br.readLine();
            for (int col = 0; col < cols; col++)
            {
                map[row][col] = line.charAt(col);
                if (map[row][col] == '0')
                    startPoint = new Point(row, col); //출발 지점을 입력받으면서 저장해둠.
            }
        }
    }
}

class MoveStat
{
    Point point;
    int moveCnt; //현재까지의 이동 횟수
    int keyBitmask; //현재 열쇠 소유 상태를 표현하는 bitmask

    public MoveStat(Point p, int moveCnt, int keyBitmask)
    {
        this.point = p;
        this.moveCnt = moveCnt;
        this.keyBitmask = keyBitmask;
    }
}

class Point
{
    int row;
    int col;

    public Point(int row, int col)
    {
        this.row = row;
        this.col = col;
    }
}