[백준] 2206. 벽 부수고 이동하기

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

2206번: 벽 부수고 이동하기

• 도착점에 가장 빠르게 도착할 수 있는 최단 거리를 구하면 되므로, bfs를 사용하면 된다.
• 그런데 벽을 한 번 부술 수 있다는 것이 관건이다.
• 처음에는 다음과 같이 풀었다.
  • Point에 x, y 위치와 지금까지 벽을 부순 적이 있는지 없는지를 의미하는 boolean destroy 변수를 정의했다.
  • 그래프를 탐색하며 벽이 아니면 이동하고, 벽이면 지금까지 벽을 부순 적이 없을 때만 벽을 부수고 이동한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int n; // 세로
    static int m; // 가로
    static int[][] map;
    static int[][] visited;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static Queue<Point> que = new LinkedList<>();

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][m];
        visited = new int[n][m];
        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split("");
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(input[j]);
            }
        }

        bfs();
    }

    private static void bfs() {
        que.add(new Point(0, 0, false));
        visited[0][0] = 1;

        while (!que.isEmpty()) {
            Point p = que.poll();
            // 도착한 경우
            if (p.x == m - 1 && p.y == n - 1) {
                System.out.println(visited[p.y][p.x]);
                return;
            }

            for (int i = 0; i < 4; i++) {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;

                // 이미 방문한 경우 이동 X
                if (visited[ny][nx] != 0) {
                    continue;
                }

                // 벽이 아닌 경우 이동
                if (map[ny][nx] == 0) {
                    visited[ny][nx] = visited[p.y][p.x] + 1;
                    que.add(new Point(ny, nx, p.destroy));
                }

                // 벽인 경우
                if (map[ny][nx] == 1) {
                    // 부신적이 없으면, 부시고 이동
                    if (!p.destroy) {
                        visited[ny][nx] = visited[p.y][p.x] + 1;
                        que.add(new Point(ny, nx, true));
                    }
                }
            }
        }

        // 도착하지 못한 경우
        System.out.println(-1);
    }

    static class Point {
        int y, x;
        boolean destroy;

        public Point(int y, int x, boolean destroy) {
            this.y = y;
            this.x = x;
            this.destroy = destroy;
        }
    }
}

• 그런데 위 방법은 정답이 아니다. 반례는 다음과 같다.
  9 9
  010001000
  010101010
  010101010
  010101010
  010101010
  010101010
  010101010
  010101011
  000100010
• 위 반례의 답으로 33이 출력되어야 하는데 이동할 수 없다고 -1이 출력된다.
• 이유는 다음과 같다.
  • 이미 방문한 위치의 경우에는 이동하지 않는 것이 문제이다!
  • 만약 벽을 부수고 특정 위치 x에 방문했다면(1), 그와 별개로 벽을 부수지 않고 천천히 x에 방문할 경우(2)
  • 벽을 부수지 않고 천천히 도착한 경우(2)에는 x에 이미 방문처리가 되어 있기 때문에 x로 이동할 수 없다.
  • 따라서 벽을 부수고 x에 먼저 도착한 경우(1)에만 x로 이동할 수 있다.
  • 그런데 만약 x로 이동한 경우가 도착점으로 가는 길에 벽을 만난다면, 이미 한 번 벽을 부쉈기 때문에 더이상 이동할 수 없어서 -1이 출력되는 것이다.
  • 즉 (2)의 경우로 도착점으로 이동할 수 있는 것인데, (1)의 경우만 고려되어 이동할 수 없다고 결과가 나오는 것이다.
• 즉, 벽을 부수며 이동하는 경우와 부수지 않고 이동하는 경우가 하나의 visited[][] 배열을 공유했기 때문에 발생하는 문제이다.
• 따라서 벽을 한 번이라도 부수며 이동하는 경우와, 부수지 않고 이동하는 경우를 분리해서 생각해야 한다.
  • 벽을 부수지 않고 이동하는 경우는 visited[0][][], 벽을 부수고 이동하는 경우는 visited[1][][]에 기록한다.
  • 만약 큐에 담긴 Point가 도착점이라면, 이는 벽을 부쉈든 부시지 않았든 최초로 도착점에 도착했다는 것이다.
  • 따라서 visited[0][n - 1][m - 1]과 visited[1][n - 1][m - 1] 중에 최댓값이 답이다. (둘 중 하나의 값은 아직 도착점에 도착하지 않았으므로 0일 것이다.)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int n; // 세로
    static int m; // 가로
    static int[][] map;
    static int[][][] visited;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static Queue<Point> que = new LinkedList<>();

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][m];
        visited = new int[2][n][m];
        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split("");
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(input[j]);
            }
        }

        bfs();
    }

    private static void bfs() {
        que.add(new Point(0, 0, false));
        visited[0][0][0] = 1;

        while (!que.isEmpty()) {
            Point p = que.poll();

            // 도착한 경우
            if (p.y == n - 1 && p.x == m - 1) {
                System.out.println(Math.max(visited[0][n - 1][m - 1], visited[1][n - 1][m - 1]));
                return;
            }

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

                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;

                /*
                벽이 아닌 경우 -> 방문한 적이 없으면 -> 이동하기
                 */
                if (map[ny][nx] == 0) {
                    // 부신 적이 없는 경우
                    if (!p.destroy && visited[0][ny][nx] == 0) {
                        visited[0][ny][nx] = visited[0][p.y][p.x] + 1;
                        que.add(new Point(ny, nx, false));
                    }
                    // 부신 적이 있는 경우
                    if (p.destroy && visited[1][ny][nx] == 0) {
                        visited[1][ny][nx] = visited[1][p.y][p.x] + 1;
                        que.add(new Point(ny, nx, true));
                    }
                }

                /*
                벽인 경우 -> 부신 적이 없고, 방문한 적이 없으면 -> 부시고 이동
                 */
                if (map[ny][nx] == 1) {
                    if (!p.destroy && visited[1][ny][nx] == 0) {
                        visited[1][ny][nx] = visited[0][p.y][p.x] + 1;
                        que.add(new Point(ny, nx, true));
                    }
                }
            }
        }

        // 도착하지 못한 경우
        System.out.println(-1);
    }

    static class Point {
        int y, x;
        boolean destroy;

        public Point(int y, int x, boolean destroy) {
            this.y = y;
            this.x = x;
            this.destroy = destroy;
        }
    }
}