[백준] 2206 - 벽 부수고 이동하기 (JAVA)

하핳 dfs bfs 이제 좀 알 것 같네^^ 하던 나에게 또 한번 고비를 안겨준 문제!
최근에는 문제 풀고 깃헙에만 올렸는데 이건 생각해볼 만한 문제인 것 같아서 오랜만에 블로그에 기록.
나중에 복기하면 좋을 만한 문제는 블로그에 쓰는 버릇을 들여야하는데 쉽지 않다....

원본 백준 문제 페이지는 링크로 남겨두기!

처음에는 단순히 벽을 부술 수 있는 기회를 같이 저장해서 이동한 위치가 0이거나 혹은 1일 때 (벽을 부술)기회가 있으면 큐에 넣고~ 아니면 말고~ 로 풀면 될 거라고 생각했다.
실제로 주어진 테스트 케이스 2개는 통과했고.
하지만 역시 채점 결과는....
그런데 아무리 생각해도 반례가 생각이 안 나서 구글에 검색해보니 친절하게 반례를 적어놓은 블로그를 발견했다.
https://dev-note-97.tistory.com/35

결국 결정적인 아이디어는 벽을 부순 경우와, 벽을 부수지 않은 경우의 거리를 따로 기록해야한다는 것이었다.
그래서 visited 배열을 map 배열에 한 차원을 더해서 벽을 부순 경우와 부수지 않은 경우를 따로 기록하도록 코드를 다시 작성하였다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// 2206 - 벽 부수고 이동하기
public class Main {
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static BufferedWriter bw;
    static int N;
    static int M;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); 
        M = Integer.parseInt(st.nextToken()); 
        int[][] map = new int[N][M];
        int[][][] visited = new int[N][M][2];

        for (int i = 0; i < N; i++) {
            String input = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = input.charAt(j) - '0';
            }
        }
        br.close();
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0, 1}); // 좌표와 벽을 부술 수 있는 개수(기회)
        visited[0][0][1] = 1;
        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            int x = poll[0];
            int y = poll[1];
            int chance = poll[2];

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (isValid(nx, ny)) {
                    // 다음 위치가 0이면 현재 chance에 해당하는 visited 배열의 그 위치의 방문 여부를 확인한다.
                    if (map[nx][ny] == 0 && visited[nx][ny][chance] == 0) {

                        // 현재 chance에 해당하는 visited 배열에 거리 + 1을 한 후 큐에 넣는다.
                        queue.offer(new int[] {nx, ny, chance});
                        visited[nx][ny][chance] = visited[x][y][chance] + 1;

                        // 다음 위치가 1이면 chance가 0인 경우(벽을 부순 상태)의 방문 배열을 확인한다.
                    } else if (map[nx][ny] == 1 && visited[nx][ny][0] == 0) {
                        // 기회가 남아 있으면
                        if (chance == 1) {
                            // 다음 위치에 해당하는 벽을 부순 경우의 방문 배열 = 현재 방문 배열의 거리 + 1
                            visited[nx][ny][0] = visited[x][y][1] + 1;
                            queue.offer(new int[] {nx, ny, 0});
                        }
                    }
                }
            }
        }
        // 방문배열 마지막이 둘 다 0이면 도달하지 못한 것이니 -1 => 
        // 둘 중 하나가 0인 경우에는 0이 아닌 것이 최종 거리 => 
        // 둘 다 0이 아닌 경우에는 둘 중 더 작은 것이 최단 거리
        int result = visited[N-1][M-1][0] == 0 && visited[N-1][M-1][1] == 0 ? -1 :
                visited[N-1][M-1][0] == 0 ? visited[N-1][M-1][1] :
                        visited[N-1][M-1][1] == 0 ? visited[N-1][M-1][0] :
                                Math.min(visited[N-1][M-1][0], visited[N-1][M-1][1]);

        bw.write(String.valueOf(result));
        bw.flush();
        bw.close();
    }

    static boolean isValid(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < M;
    }
}