[BOJ] 2206. 벽 부수고 이동하기 (Java)

[BOJ] 2206. 벽 부수고 이동하기 (Java)

Problem

제출일 : 2020-03-07

문제 풀이 시간 : 2H

난이도 : ★★★☆

---

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

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

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

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

input

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

Output

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

Example

input

6 4
0100
1110
1000
0000
0111
0000

output

15

Solution & Inpression

[Hint][https://www.acmicpc.net/board/view/27386]

1. 가중치가 없는 최단 경로는 무조건 BFS입니다. 왜 DFS가 안 될까요? 그 이유는 당연하게도, 특정 칸에 처음 도달했을 때까지의 경로의 길이가 다른 경로를 통해 도달한 길이보다 짧다는 보장이 전혀 없기 때문입니다. 아직까지 이 사실을 모르고 계셨다면, 이 문제는 아직 풀기에 너무 어렵습니다. 더 기본적인 BFS 문제들을 먼저 풀어보세요.

2. 모든 칸을 전부 0으로 하나씩 바꾸어보고 BFS를 돌리는 것을 반복해서는 통과될 수 없습니다. 대부분의 알고리즘 문제가 그렇듯이, 풀이를 짜기 전에 반드시 해야 하는 것 중 하나는 시간 복잡도를 생각하는 것입니다. 시간 복잡도 계산, 전혀 어렵지 않습니다. 벽이 최대 O(NM)개 있는 맵에서, 벽을 하나 부술 때마다 O(NM)개의 칸을 탐색해야 하죠? 그러니 O((NM)^2)입니다. 이 수는 우리가 대충 1초에 돌 수 있다고 보는 단위인 1억을 10000배나 뛰어넘는 1조입니다. 절대 통과될 수 없겠죠?

3. 칸마다 방문 체크 하나씩만 하는 방법으로는 풀 수 없습니다. 어떤 칸에 도달했을 때 나는 "아직 벽을 부술 수 있는 상태"일 수도 있고, "더 이상 벽을 부술 수 없는 상태"일 수도 있습니다. 큐에 그 상태를 넣은 것만으로 되는 것이 아닙니다. 당장 이 지점까지 어떻게든 최단으로 오는 길만 구했다고 해서, 그 이후의 여정도 최적으로 만들 수 있는 건 아닙니다.

Code

언어 : JAVA

메모리 : 137144 kb

실행 시간 : 628 ms

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int N, M, ans;
    static char[][] map;

    static int dr[] = { -1, 1, 0, 0 };
    static int dc[] = { 0, 0, 1, -1 };

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        M = sc.nextInt();

        map = new char[N][M];
        for (int i = 0; i < N; i++) {
            String str = sc.next();
            for (int j = 0; j < M; j++) {
                map[i][j] = str.charAt(j);
            }
        }
        ans = -1;
        BFS();
        System.out.println(ans);
    }

    private static void BFS() {
        boolean visit[][][] = new boolean[2][N][M];

        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] { 0, 0, 0, 1 });
        visit[0][0][0] = true;

        while (!q.isEmpty()) {
            int[] now = q.poll();

            if (now[0] == N - 1 && now[1] == M - 1) {
                ans = now[3];
                break;
            }

            for (int dir = 0; dir < 4; dir++) {
                int nr = now[0] + dr[dir];
                int nc = now[1] + dc[dir];
                if (isRange(nr, nc) && !visit[now[2]][nr][nc]) {
                    if (map[nr][nc] == '0') {
                        visit[now[2]][nr][nc] = true;
                        q.offer(new int[] { nr, nc, now[2], now[3] + 1 });
                    } else if (now[2] == 0) {
                        visit[1][nr][nc] = true;
                        q.offer(new int[] { nr, nc, 1, now[3] + 1 });
                    }
                }
            }
        }
    }

    private static boolean isRange(int r, int c) {
        if (0 <= r && r < N && 0 <= c && c < M)
            return true;
        return false;
    }
}