백준 2206 - 벽 부수고 이동하기

문제

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

리뷰

BFS 내부적으로 벽을 부순 경우에 따라 방문 처리를 다르게 설정하는 로직을 추가하여
풀이할 수 있는 문제였다.

문제 조건에 따라 생각을 해보면 벽을 부순 경로는 벽을 부수지 않은 경로보다 짧을 때
가능하다. 이 말인 즉슨, 벽을 부순 경로와 벽을 부수지 않은 경로를 별도로 계산해줄
필요가 있다는 뜻이다. 우선 BFS 진행에 활용하기 위해 좌표, 비용, 벽을 부순 여부를
저장하는 Node 클래스를 정의하였다. 또한, 개별 방문 처리를 위해 visited와
crashVisited를 설정하였다.

BFS 내부에서는 다음 3가지 탐색 조건을 구현하였다.

• 다음 탐색하려는 좌표가 벽일때
  벽을 부수고 탐색하는 것은 벽을 부수지 않은 경로일 때 가능하다. (!current.crash)
  또한 벽을 부수기 때문에 crashVisited에 방문 처리를 기록해준다.
• 다음 탐색하려는 좌표가 벽이 아닐때
  • 벽을 부수지 않은 경로라면 visited에 방문 처리를 기록한다.
  • 벽을 부순 경로에서 탐색을 진행한다면 crashVisited에 방문 처리를 기록한다.

위 과정을 통해 최단 경로 비용을 도출할 수 있다.

로직의 시간복잡도는 BFS의 복잡도로 포함하므로 $O(N)$ 으로 수렴하고 이는 최악의 경우인
1000에서도 무난히 2초의 제한 조건을 통과한다.

코드

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

import static java.lang.Integer.parseInt;

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

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        StringTokenizer st = new StringTokenizer(in.nextLine());
        N = parseInt(st.nextToken());
        M = parseInt(st.nextToken());

        map = new int[N][M];
        visited = new boolean[N][M];
        crashVisited = new boolean[N][M];

        for (int y = 0; y < N; y++) {
            String line = in.nextLine();
            for (int x = 0; x < M; x++)
                map[y][x] = line.charAt(x) - '0';
        }

        Node start = new Node(0, 0, 1, false);
        Node end = new Node(M - 1, N - 1, 0, false);
        int result = bfs(start, end);

        System.out.print(result);
        in.close();
    }

    static int bfs(Node start, Node end) { 
        Queue<Node> queue = new ArrayDeque<>();
        queue.offer(start);
        visited[start.y][start.x] = true;
        crashVisited[start.y][start.x] = true;

        int[] px = {-1, 1, 0, 0};
        int[] py = {0, 0, -1, 1};

        while (!queue.isEmpty()) {
            Node current = queue.poll();

            if (current.x == end.x && current.y == end.y) {
                return current.level;
            }

            for (int i = 0; i < px.length; i++) {
                int nx = current.x + px[i];
                int ny = current.y + py[i];

                if (nx < 0 || nx >= M || ny < 0 || ny >= N)
                    continue;

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

        return -1;
    }

    static class Node {
        int x, y, level;
        boolean crash;

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

결과