문제 설명

N * M 행렬에서 0은 이동할 수 있고, 1은 이동할 수 없는 벽이다.
최단 경로로 (1,1)에서 (N,M)으로 가는 경로 길이를 구해라. 단, 필요하다면 벽을 딱 한 번 부술 수 있다.

시간 2초, 공간 192MB

문제 접근 1차

BFS를 오랜만에 풀어서 최단 경로를 구해야 한다는 점을 보고도 난 DFS로 시도했다. 이게 이 문제를 풀기 더 쉬운 접근이라고 생각했나보다. 결국 시간초과가 났다. 잘생각해보면 DFS는 그냥 완전탐색이나 DP에 같이 겸용으로 쓰는 식으로만 사용했었다. 그래도 나름 백트래킹도 적용해보려고(이걸 넣으니 2퍼까지는 올라가서 시간초과남) 하고 시간을 단축하려고 했지만 DFS로는 시간초과 해결을 못했다.

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

public class Main {
    static int N, M;
    static int[][] map;
    static boolean[][] isVisited;
    static int INF = 10_0000_0000;
    static int result = INF;

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N + 1][M + 1];
        isVisited = new boolean[N + 1][M + 1];
        String input;
        for (int i = 1; i <= N; i++) {
            input = br.readLine();
            for (int j = 1; j <= M; j++) {
                map[i][j] = input.charAt(j - 1) - 48;
            }
        }

        isVisited[1][1] = true;
        dfs(1, 1, false, 1);
        if (result == INF) {
            System.out.println(-1);
        } else {
            System.out.println(result);
        }
    }

    static void dfs(int row, int col, boolean isBreak, int depth) {
        if (row == N && col == M) {
            result = Math.min(result, depth);
            return;
        }

        if (depth + (N - row) + (M - col) >= result) return; // 더 볼 이유 없음.
        for (int i = 0; i < 4; i++) {
            int nextRow = row + dx[i];
            int nextCol = col + dy[i];
            if (isIn(nextRow, nextCol) && !isVisited[nextRow][nextCol]) {
                if (map[nextRow][nextCol] == 1 && !isBreak) {
                    isVisited[nextRow][nextCol] = true;
                    dfs(nextRow, nextCol, true, depth + 1);
                    isVisited[nextRow][nextCol] = false;
                } else if (map[nextRow][nextCol] == 0) {
                    isVisited[nextRow][nextCol] = true;
                    dfs(nextRow, nextCol, isBreak, depth + 1);
                    isVisited[nextRow][nextCol] = false;
                }
            }
        }
    }

    static boolean isIn(int row, int col) {
        return row >= 1 && row <= N && col >= 1 && col <= M;
    }
}

문제 접근 2차

사실 위에서 DFS로 삽질해서 뇌가 좀 지친 상태였더 것 같다. BFS로 풀려고 바꿔봤으나 그동안 풀어왔던 일반적인 BFS 로는 되지 않았고 무언가 특별한게 더 필요하단 걸 알았다. 원인은 명백하게 이미 벽을 부순 경로탐색과 아직 벽을 부수지 않은 경로탐색 간에 isVisited 방문 처리가 중첩되는 문제였다.
하지만, 배열을 분리하기에는 스스로 머리가 정리가 되지 않고 엉킨 느낌이였다.
결국 검색을 했고, 다음 블로그에서 내 엉킨 생각을 풀어주는 이해가 잘되는 이미지를 봤다.
https://iseunghan.tistory.com/316

결국 문제는

결국 문제는 이거였다. 한 번 벽을 뚫어 간 경로가 방문여부를 체크할 방문배열과, 아직 벽을 뚫지 않은 경로를 위한 방문 여부를 만드는 것이다. 잘 생각해보자.
이미 벽을 뚫은 경로A와 이미 벽을 뚫은 경로B가 있는데, BFS에서 A가 먼저 등장했다고 하자. 그 말은 B가 앞으로 이동하다가 A가 지나온 경로를 밟을 필요가 없다는 것임. 이는 어차피 A의 경로에서 최단거리가 나온다면 B에서 A로 갈아탄 것보다 애초에 A에서 이동한게 더 빠르단걸 의미하기 때문이다. 즉 BFS의 본질적인 원리를 잘 이해하고 기억하고 있었다면 이 문제를 어렵지 않게 풀었을 것 같다.... 역시 근본을 가장 잘 알고 있는게 제일 중요한 것 같다.
요즘 문제를 너무 뜸하게 풀면서 BFS를 오랜만에 풀어서 기계식으로 해결하다보니 머릿속의 뭉친 실타래가 풀리지 않았던것 같다.

풀이

솔직히 코드가 막 깔끔한지는 모르겠다. 코드 depth도 좀 깊은 것 같고, 함수 분리가 하고 싶지만 요즘 할게 너무 많아서 백준에서는 생략...

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

public class Main {
    static int N, M;
    static int[][] map;
    static boolean[][] isNonBreakVisited;
    static boolean[][] isAlreadyBreakVisited;
    static int INF = 10_0000_0000;
    static int result = INF;

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N + 1][M + 1];
        isNonBreakVisited = new boolean[N + 1][M + 1];
        isAlreadyBreakVisited = new boolean[N + 1][M + 1];
        String input;
        for (int i = 1; i <= N; i++) {
            input = br.readLine();
            for (int j = 1; j <= M; j++) {
                map[i][j] = input.charAt(j - 1) - 48;
            }
        }

        if (N == 1 && M == 1) {
            System.out.println(1);
            return;
        }

        System.out.println(bfs());
    }

    static int bfs() {
        LinkedList<Node> q = new LinkedList();
        q.add(new Node(1, 1, false, 1));
        isNonBreakVisited[1][1] = true;

        while (!q.isEmpty()) {
            Node curN = q.poll();
            for (int i = 0; i < 4; i++) {
                int nextRow = curN.r + dx[i];
                int nextCol = curN.c + dy[i];
                if (isIn(nextRow, nextCol)) {
                    if (curN.isBreak && map[nextRow][nextCol] == 1) continue;
                    if (curN.isBreak) {
                        if (!isAlreadyBreakVisited[nextRow][nextCol]) {
                            isAlreadyBreakVisited[nextRow][nextCol] = true;
                            q.add(new Node(nextRow, nextCol, true, curN.depth + 1));
                        }
                    } else {
                        if (map[nextRow][nextCol] == 0) {
                            if (!isNonBreakVisited[nextRow][nextCol]) {
                                isNonBreakVisited[nextRow][nextCol] = true;
                                q.add(new Node(nextRow, nextCol, false, curN.depth + 1));
                            }
                        } else {
                            if (!isAlreadyBreakVisited[nextRow][nextCol]) {
                                isAlreadyBreakVisited[nextRow][nextCol] = true;
                                q.add(new Node(nextRow, nextCol, true, curN.depth + 1));
                            }
                        }
                    }
                }
                if (nextRow == N && nextCol == M) return curN.depth + 1;
            }
        }
        return -1;
    }

    static class Node {
        int r;
        int c;
        boolean isBreak;
        int depth;

        Node(int r, int c, boolean isBreak, int depth) {
            this.r = r;
            this.c = c;
            this.isBreak = isBreak;
            this.depth = depth;
        }
    }

    static boolean isIn(int row, int col) {
        return row >= 1 && row <= N && col >= 1 && col <= M;
    }

}

배운점
최단경로를 그래프에서 구하는 문제라면, 때려죽여도 BFS임.
BFS에서 특정 상태별로 경로에 중첩이나 서로 영향을 준다면, 상태별로 방문 배열을 분리해라.
BFS는 최악의 경우에도 O(N^2) 이라는걸 다시 떠올리자. 완전탐색이 아닌 이상 DFS보다 훨씬 빠를 가능성이 매우 높다.
아, 그리고 BFS 풀때 방문배열 true로 만드는건 다음노드를 큐에 넣어야할때만 해줘라. 그동안 BFS 좀 비효율적으로 푼 것 같다.