백준 14442 - 벽 부수고 이동하기 2

문제

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

리뷰

벽 부수고 이동하기 시리즈의 두번째 문제였다. 이전과 달리 벽을 $K$번까지 부술
수 있다는 조건이 추가되었다.

조건을 충족시키기 위해 경로를 벽을 부순 횟수에 따라 도출할 수 있도록
visited를 $K \times N \times M$의 형태로 선언했다.
bfs 로직에서는 다음과 같은 순서로 경로를 탐색한다.

• 다음 경로가 벽이 아닐 경우 미방문시 방문 처리한다.
• 다음 경로가 벽일 경우 벽을 아직 부술 수 있으며(node.k+1<=K)
  방문하지 않은 경우 방문 처리한다.

벽을 부순 횟수에 따라 visited[k]에 다르게 처리하는 것이 관건이다.

로직의 시간 복잡도는 bfs의 $O(K \times N \times M)$꼴로 수렴하며
최악의 경우 $10^7$의 연산을 수행하므로 제한 조건인 2초를 무난히 통과한다.

코드

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

import static java.lang.Integer.parseInt;

public class Main {
    static int[][] map;
    static boolean[][][] visited;
    static int N, M, K;

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

        map = new int[N][M];
        visited = new boolean[K + 1][N][M];

        for (int y = 0; y < map.length; y++) {
            String line = br.readLine();
            for (int x = 0; x < map[y].length; x++)
                map[y][x] = line.charAt(x) - '0';
        }

        int result = bfs();
        System.out.println(result);
        br.close();
    }

    static int bfs() { // O(K x N x M), 최악의 경우 10 x 1000 x 1000 = 10^7
        Queue<Node> queue = new ArrayDeque<>();
        queue.offer(new Node(0, 0, 0, 1));
        for (int i = 0; i <= K; i++)
            visited[i][0][0] = true;

        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        int nx, ny;

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            if (node.x == M - 1 && node.y == N - 1)
                return node.level;

            for (int i = 0; i < dx.length; i++) {
                nx = node.x + dx[i];
                ny = node.y + dy[i];

                if (isOut(nx, ny))
                    continue;

                if (map[ny][nx] == 1) {
                    if (node.k + 1 > K)
                        continue;

                    if (visited[node.k + 1][ny][nx])
                        continue;

                    visited[node.k + 1][ny][nx] = true;
                    queue.offer(new Node(nx, ny, node.k + 1, node.level + 1));
                } else {
                    if (!visited[node.k][ny][nx]) {
                        visited[node.k][ny][nx] = true;
                        queue.offer(new Node(nx, ny, node.k, node.level + 1));
                    }
                }
            }
        }

        return -1;
    }

    static boolean isOut(int x, int y) {
        return x < 0 || x >= M || y < 0 || y >= N;
    }

    static class Node {
        int x, y, k, level;

        public Node(int x, int y, int k, int level) {
            this.x = x;
            this.y = y;
            this.k = k;
            this.level = level;
        }
    }
}

결과