[백준/BOJ] 16933번 벽 부수고 이동하기 3 (자바/Java)

---

1. 문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 이동하지 않고 같은 칸에 머물러있는 경우도 가능하다. 이 경우도 방문한 칸의 개수가 하나 늘어나는 것으로 생각해야 한다.

이번 문제에서는 낮과 밤이 번갈아가면서 등장한다. 가장 처음에 이동할 때는 낮이고, 한 번 이동할 때마다 낮과 밤이 바뀌게 된다. 이동하지 않고 같은 칸에 머무르는 경우에도 낮과 밤이 바뀌게 된다.

만약에 이동하는 도중에 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K개 까지 부수고 이동하여도 된다. 단, 벽은 낮에만 부술 수 있다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

 

2. 풀이

만약 벽 부수고 이동하기 시리즈를 1부터 차례대로 풀었다면, 사실 문제 접근방법이 비슷해서 난이도가 높은 문제(골드 1)임에도 불구하고 풀었을 것이다.

 

벽 부수고 이동하기 1, 2와 같이 우선 부셨음을 표시하는 차원이 하나 더 필요하므로, distance는 3개의 차원을 갖도록 만든다. 여기서 달라진 점은, 낮과 밤이 존재하여 밤에는 벽을 부술 수 없다는 전제이다.

 

나는 그래서, 큐에 낮과 밤을 표시하는 0과 1을 그리고 다음 distance에 얼마나 더해줘야하는지를 나타내는 plusAmount를 추가해주었다.

 

기존에는 다음 단계를 넘어갈 때마다 distance[xNew][yNew] = distance[x][y]+1 과 같은 방식을 썻겠지만, 여기서는 1이 아닌 2를 더해줘야하는 경우(밤일 때는 벽을 부실 수 없으므로, 낮까지 기다렸다가 벽을 부시게 되는 경우)가 있으므로 distance[xNew][yNew] = distance[x][y] + plusAmount와 같이 사용했다.

 

그리고, 만약 밤이고 부셔야하는 상황 큐에 {x, y}를 넣어줬다. 기존에는 {xNew, yNew}를 넣었지만, 지금은 밤이므로 낮까지 기다려야하기에 큐에 한번 더 추가한 셈이다. 그렇게 하고 plusAmount를 1이 아닌 2를 넣어주면 된다.

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 M;
    static int N;
    static int K;
    static int[][] input;
    static int[][][] distance;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int res = 1000002;

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

        input = new int[M][N];
        distance = new int[M][N][K+1];

        for(int i=0; i<M; i++){
            String[] tmp = br.readLine().split("");
            for (int j = 0; j < N; j++) input[i][j] = Integer.parseInt(tmp[j]);
        }

        BFS();
        System.out.println(res);
    }

    private static void BFS() {
        Queue<int[]> q = new LinkedList<>();
        distance[0][0][0] = 1; // 처음과 마지막의 값도 카운트하므로 1로 시작한다.
        q.add(new int[]{0, 0, 0, 1, 1}); // 첫 번째 이동 중에는 벽을 부실 수 있다. 그러므로 초기에 1을 넣어줘야, 아래의 canBreak가 true가 된다.

        while(!q.isEmpty()){
            int[] tmp = q.poll();
            int x = tmp[0];
            int y = tmp[1];
            int power = tmp[2]; // 얼마나 부셨는지!
            int noon = tmp[3];
            int plusAmount = tmp[4]; // 밤이 되면, 부시지 못하기 때문에 낮이 될 때, 2를 더해주는 변수이다.
            int nextNoon = noon==0?1:0; // 다음 noon을 가리킨다. 1이면 0, 0이면 1로 바꿔준다.
            boolean canBreak = noon != 0; // 밤인지 낮인지, 즉 부실 수 있는지 없는지를 나타낸다.

            if(x==M-1 && y==N-1){ // 찾았다면 갱신하고 return
                res = Math.min(distance[x][y][power], res);
                return;
            }

            for(int i=0; i<dx.length; i++){
                int xNew = x + dx[i];
                int yNew = y + dy[i];

                if(xNew >= 0 && xNew < M && yNew >= 0 && yNew < N){
                    if(distance[xNew][yNew][power]==0 && input[xNew][yNew]==0){ // 다음이 0이라면 낮밤 상관없이 go
                        distance[xNew][yNew][power] = distance[x][y][power]+plusAmount;
                        q.add(new int[]{xNew, yNew, power, nextNoon, 1}); // plusAmount는 밤인데, 다음에 도달할 부분이 1인 때만 고려함.
                    }

                    if(power < K) {
                        // 부실 수 있고(낮이고), 다음이 1이라면 power를 증가시키고, 갱신
                        if(distance[xNew][yNew][power + 1] == 0 && input[xNew][yNew] == 1 && canBreak) {
                            distance[xNew][yNew][power + 1] = distance[x][y][power] + plusAmount;
                            q.add(new int[]{xNew, yNew, power+1, nextNoon, 1});

                        // 만약 밤인데, 다음이 1이라면 plusAmount를 1 증가시키고, 기존 x, y값을 큐에 넣는다.
                        // 이렇게 되면, 다음 1을 부시려고 할 떄, 2가 더해지므로, 우리가 원하는 값이 나온다.
                        } else if (distance[xNew][yNew][power + 1] == 0 && input[xNew][yNew] == 1 && !canBreak) {
                            q.add(new int[]{x, y, power, nextNoon, plusAmount+1});
                        }
                    }
                }
            }
        }
        res = -1; // 찾지 못하면, -1을 반환.
    }
} .

 

3. 결과

 

4. 총평

 - 생략