문제해설

BFS 알고리즘을 사용한 가장 기본적인 미로에서 최단경로 찾기 문제에서 벽을 한칸만 없앨수 있도록 변형시킨 문제이다. 지금은 없지만 혹시나 이 글을 읽으시는 분들 중 BFS를 모르시는 분을 위해 나중에 BFS알고리즘에 대한 글을 작성해 태그해놓도록 하겠다. (아무도 안볼거같긴 하지만..)
이 문제의 핵심은 벽을 한칸 없애는 기능을 사용 했는지 안했는지를 구분해서 방문처리를 각각 해줘야 하는 것이다.

BFS, Graph

일단 벽을 없애는 기능을 사용 했는지 안했는지만 체크해주면 되고 방문처리는 상관 없다고 생각하는 사람들이 분명히 있을것이다. (왜냐면 내가 그랬다 ㅎ)
그 사람들을 위해 간단하게 설명하겠다.

다음과 같은 맵이 주어졌다고 해보자. S 에서 출발해서 E에 도착해야한다. 만약 S지점에서 위쪽으로 벽을 부수고 2칸 이동했다면 해당 지점은 방문처리가 될것이다.

이미 2칸을 이동한뒤 방문처리가 되어있기때문에 벽을 부수지 않고 아래쪽으로 돌아왔다면 8칸을 이동해야 하므로 이미 2칸으로 이동한 경로때문에 방문처리가 되어 해당 지점을 고려하지 않게 된다.

하지만 제일 아래 그림처럼 벽을 부수지 않고 8칸을 이동한 뒤 위쪽 벽을 부수고 도착지점으로 가는 것이 제일 빠른 경로이다. 따라서 벽을 부순 경우와 그렇지 않은 경우에 대해서 방문처리를 따로 해줘야 한다.

시간복잡도

맵의 모든 위치를 탐색하는데 N * M번의 횟수가 필요하고 벽을 아직 안부순 경우와 부순 경우 두 경우로 방문처리를 나누기 때문에 최대 2 * (N * M) 번의 횟수가 필요하다. 따라서 시간복잡도는 O(N * M) 이다. (N <= 1000, M <= 1000)

코드

import java.io.*;
import java.util.*;

public class Main {
    static int N, M, map[][];
    static int drow[] = {1, -1, 0, 0}, dcol[] = {0, 0, 1, -1};
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = null;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = s.charAt(j) - '0';
            }
        }
        if (N == 1 && M == 1) bw.write("1");
        else bw.write(String.valueOf(bfs()));
        bw.flush();
        bw.close();
    }

    static int bfs() {
        int min = Integer.MAX_VALUE;

        Queue<node_2206> queue = new LinkedList<>();
        boolean visit[][][] = new boolean[N][M][2];
        queue.offer(new node_2206(0, 0, 1, false));

        while (!queue.isEmpty()) {
            node_2206 n = queue.poll();

            for (int i = 0; i < 4; i++) {
                int r, c;
                r = n.row + drow[i];
                c = n.col + dcol[i];

                if (r < 0 || c < 0 || N <= r || M <= c) continue;
                if (n.used) {
                    if (map[r][c] == 1 || visit[r][c][1]) continue;
                    if (r == N - 1 && c == M - 1) return n.count + 1;
                    queue.offer(new node_2206(r, c, n.count + 1, true));
                    visit[r][c][1] = true;
                }
                else {
                    if (map[r][c] == 1) {
                        if (visit[r][c][1]) continue;
                        queue.offer(new node_2206(r, c, n.count + 1, true));
                        visit[r][c][1] = true;
                    }
                    else {
                        if (visit[r][c][0]) continue;
                        if (r == N - 1 && c == M - 1) return n.count + 1;
                        queue.offer(new node_2206(r, c, n.count + 1, false));
                        visit[r][c][0] = true;
                    }
                }

            }
        }
        return -1;
    }
}

class node_2206 {
    int row, col, count;
    boolean used;
    node_2206(int row, int col, int count, boolean used) {
        this.row = row;
        this.col = col;
        this.count = count;
        this.used = used;
    }
}