[Java] 백준 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을 출력한다.

 

문제 링크 : 달이 차오른다, 가자.

---

설명

이 문제에서는 생각해줘야 할 부분 두 가지가 있다.

1. 열쇠를 어떻게 저장할 것인가?

2. 방문여부를 어떻게 체크할 것인가?

 

1. 열쇠를 어떻게 저장할 것인가?

처음에 set으로 중복없이 하면 된다고 생각하여 set으로 넣어주었다.

그리고 문을 만나면 set에서 해당 키가 있는지 검색하고 있으면 지나가는 식으로 구현을 했는데 그렇게 하게 되면 일단 해당 문에 맞는 열쇠를 모두 대문자로 저장해야하며 방문 여부를 알기가 힘들다. 

 

이 문제는 특이하게 지나왔던 길을 다시 지나가야하는 문제이므로 방문 여부를 잘 나눠서 저장해야한다.

아래 그림을 보면 0에서 출발하여 f 열쇠를 얻고 다시 0을 지나 .으로 가야한다.

이 부분에서 비트마스킹을 사용해 열쇠를 저장하고 그에 따른 방문여부를 저장하면 된다. 

 

2. 방문여부를 어떻게 체크할 것인가?

비트마스킹이 갑자기 왜 나오냐하면 열쇠 종류를 2진수로 변경하여 종류별로 방문 배열을 체크하면 각각의 종류에 따라 중복되지 않게 갈 수 있기 때문이다. 

아 이 말은 내가 적었지만서도 이해하기 어려운 말인 것 같다.

 

위 그림을 예시로 f라는 열쇠는 2진수로 변경하면 100000 가 될 것이다.

F에 해당하는 문을 만났을 때 변경한 2진수로 열쇠가 있는지 없는지를 확인하면 된다.

만약 f 열쇠를 얻고 a 열쇠를 얻으면 2진수는 100001 가 된다.

 

그렇다면 열쇠 종류로 방문배열을 저장하는 것은 무슨 의미인가?

a 열쇠만 있는 경우 => 000001 

b 열쇠만 있는 경우 => 000010

a,b 열쇠를 가지고 있는 경우 => 000011

a,b,c 열쇠를 가지고 있는 경우 => 000111

 

위 경우에 따라 방문 체크를 해 줄 것이고, 지금 지나온 길과 키를 얻고 다시 지나가는 것은 다른 의미를 가지기 때문에 따로 보관을 해두는 것이다.

 

방문 배열은 visited[64][n][m]  3차원 배열로 선언했고 64는 무엇을 의미하는가

아까 열쇠를 기준으로 방문 배열을 저장한다고 했다.

열쇠는 6가지 ,비트로 표현하면 111111 모든 열쇠를 다 가지고 있다면 2^6 = 64 가 되므로 64로 선언해준다.

 

거리는 save라는 배열을 이용해 저장해주었다.

. 0 1을 만날때에는 큐에 값을 넣어주면서 거리를 업데이트 해주었다.

열쇠를 만날때에는 해당 열쇠를 2진수로 변경하여 방문여부를 체크하고 큐에 값을 넣어주었고,

문을 만나면 현재 열쇠가 문에 맞는 열쇠가 있는지 확인 후 (0보다 크다면 있다는 의미) 있다면 해당 위치를 방문 체크를 해준다.

 

최종적으로 탈출할 수 있는 최솟값을 알기위해 save배열을 돌면서 ans를 최솟값으로 업데이트 해준다. 

만약 ans가 Integer.MAXVALUE라면 탈출하지 못했다는 의미이므로 -1을 출력해준다.

코드

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

public class Main {
    static String[][] map;  // 미로 저장 배열
    static int[][] save; // 거리 저장 배열
    static boolean[][][] visited;   // 방문 여부 체크
    static int n, m;    // 세로, 가로
    static int ans = Integer.MAX_VALUE; // 최소 거리
    static int[] dx = {0, 1, 0, -1};    // 상하
    static int[] dy = {1, 0, -1, 0};    // 좌우
    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());
        map = new String[n][m]; save = new int[n][m];
        visited = new boolean[64][n][m];    // 비트마스킹 기준 6개의 열쇠 종류 = 64
        for (int i = 0; i < n; i ++){
            String[] s = br.readLine().split("");
            for (int j = 0; j < m; j++){
                map[i][j] = s[j];
                save[i][j] = Integer.MAX_VALUE; // 모든 값을 최대값으로
            }
        }
        for (int i = 0; i < n; i ++){
            for (int j = 0; j < m; j++){
                if (map[i][j].equals("0")) {    // 시작부분부터 탐색
                    save[i][j] = 0;     // 시작부분 값 초기화
                    bfs(i, j);
                }
            }
        }
        for (int i = 0; i < save.length; i++) {
            for (int j = 0; j < save[i].length; j++) {
                // 탈출했다면 가장 짧은 거리로 변경
                if (map[i][j].equals("1")) ans = Math.min(ans, save[i][j]);
            }
        }
        // ans가 최대값이 아니라면 방문을 했다는 의미이므로 결과값 출력
        System.out.println((ans == Integer.MAX_VALUE) ? -1 : ans);
    }
    static void bfs(int x ,int y){
        Queue<int[]> q = new LinkedList<>();
        // 행, 열, 깊이, 열쇠 종류
        q.offer(new int[]{x, y, 0, 0});
        visited[0][x][y] = true;
        while (!q.isEmpty()){
            int[] now = q.poll();

            if (map[now[0]][now[1]].equals("1")) break;

            for (int i = 0; i<4; i++){
                int nx = dx[i]+now[0];
                int ny = dy[i]+now[1];

                if (isBoundary(nx, ny) && !map[nx][ny].equals("#") && !visited[now[3]][nx][ny]){ // 벽 x, 방문 x
                    if (map[nx][ny].equals(".") || map[nx][ny].equals("1") || map[nx][ny].equals("0")){ // .이거나 / 1거나 / 0일 경우
                        q.offer(new int[]{nx, ny, now[2] + 1, now[3]});
                        save[nx][ny] = Math.min(save[nx][ny], now[2] + 1);
                        visited[now[3]][nx][ny] = true;
                    }

                    else if (map[nx][ny].equals("a") || map[nx][ny].equals("b") || map[nx][ny].equals("c") || map[nx][ny].equals("d")
                            || map[nx][ny].equals("e") || map[nx][ny].equals("f")) {
                        int nk = 1 << (map[nx][ny].charAt(0) - 'a');
                        nk = nk | now[3];
                        if (!visited[nk][nx][ny]) {
                            visited[now[3]][nx][ny] = true;
                            visited[nk][nx][ny] = true;
                            q.offer(new int[]{nx, ny, now[2] + 1, nk});
                            save[nx][ny] = Math.min(save[nx][ny], now[2] + 1);
                        }
                    }
                    else if (map[nx][ny].equals("A") || map[nx][ny].equals("B") || map[nx][ny].equals("C") || map[nx][ny].equals("D")
                            || map[nx][ny].equals("E") || map[nx][ny].equals("F")) {
                        int d = 1 << (map[nx][ny].charAt(0) - 'A');
                        if ((now[3] & d) > 0) {  // 현재 열쇠 값과 문에 해당하는 2진수의 값이 0보다 큰 경우(열 수 있는 경우)
                            visited[now[3]][nx][ny] = true;
                            save[nx][ny] = Math.min(save[nx][ny], now[2] + 1);
                            q.offer(new int[]{nx, ny, now[2] + 1, now[3]});
                        }
                    }
                }
            }
        }
    }
    static boolean isBoundary(int nx, int ny){
        return nx >= 0 && nx < n && ny >= 0 && ny < m;
    }
}