[골드3, BFS] 백준 2206 - 벽 부수고 이동하기 (자바)

Think

1. 처음에는 벽 위치를 저장해두고, 하나씩 벽을 없애면서 모든 경우의 수를 dfs 했다.
2. 그런데… 알고보니 시간복잡도가 NM^2였다.
3. https://kscodebase.tistory.com/66를 참고했다.
4. int[][][] isVisited를 활용하여, 벽을 뿌신 경우와 안뿌신 경우를 구분해서 관리할 수 있었다.
5. DFS는 가중치가 없을 경우(다익스트라를 사용하지않아도 되는 경우), 무조건 최단거리를 보장한다.
6. 또한, Queue 특성상, 벽을 뚫고 가는 경우와 안뚫고 돌아가는 경우 모두 체크가 가능하다
   • 이 개념이 이 문제를 푸는 아이디어를 이해하는데에 중요한 포인트라고 생각한다
     • 왜냐면….
       1. 벽을 안 부수고도 현재 칸까지 도달이 가능하지만, 벽을 부수고 오는 것이 더 짧다고 가정해봅시다. 현재 지점에서 목표 지점까지 가려면 무조건 벽을 한 개 부숴야만 된다고 해봅시다. 비록 현재 칸까지는 벽을 부수고 오는 것이 최적이었지만, 이 상태로는 끝에 아예 도달을 못 하죠? 현재 칸까지는 더 멀더라도 벽을 안 부수고 와야, 끝에 도달이 가능합니다.
       2. 현재 칸까지 벽을 안 부수고 최단으로 올 수 있었다고 가정해봅시다. 현재 지점에서 목표 지점까지 가는 데에, 벽을 한 개 부수고 가는 것이 안 부수고 가는 것보다 최적이 나온다고 해봅시다. 그렇다면 지금 내가 벽을 더 부술 수 있는 상태라는 사실을 알고 있어야만 할 것입니다.
     • 라는 케이스까지 다 탐색할 수 있기 떄문!
7. if(isVisited[position.breakingFlag][mr][mc] > 0) continue; 의 조건도 중요하다.
   • BFS를 통해 특정 지점에 왔다는건 최단 거리로 왔다는 의미이기 때문에, breakingFlag가 어떤 상태이든 이미 들른 곳이라면 패스!

 

 

 

정답코드

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

public class test {
    static int N, M, result;
    static int[][] map;
    static int[][][] isVisited;

    static int[] dr = new int[]{0,0,1,-1};
    static int[] dc = new int[]{1,-1,0,0};
    static StringBuilder sb = new StringBuilder();
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;


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

        process();
    }

    private static void process() {

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

    private static int bfs() {
        Queue<Position> q = new LinkedList<>();
        isVisited[0][0][0] = 1;
        q.add(new Position(0,0,0));

        while(!q.isEmpty()){
            Position position = q.poll();

            if(position.r == N-1 && position.c == M-1) return isVisited[position.breakingFlag][position.r][position.c];

            for (int i = 0; i < 4; i++) {
                int mr = position.r + dr[i];
                int mc = position.c + dc[i];
                int nextBreakingFlag = position.breakingFlag;

                if(mr < 0 || mc < 0 || mr>= N || mc >= M)   continue;
                if(isVisited[position.breakingFlag][mr][mc] > 0) continue;

                if(map[mr][mc] == 0){
                    isVisited[nextBreakingFlag][mr][mc] = isVisited[position.breakingFlag][position.r][position.c] + 1;
                    q.add(new Position(mr,mc, position.breakingFlag));
                }
                if(map[mr][mc] == 1 && nextBreakingFlag == 0){
                    isVisited[1][mr][mc] = isVisited[position.breakingFlag][position.r][position.c] + 1;
                    nextBreakingFlag = 1;
                    q.add(new Position(mr,mc, nextBreakingFlag));
                }
            }
        }

        return -1;

    }

    private static void init() throws IOException {
        st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        isVisited = new int[2][N][M];

        for (int i = 0; i < N; i++) {
            char[] inputs = br.readLine().toCharArray();

            for (int j = 0; j < M; j++) {
                map[i][j] = inputs[j] - '0';
            }
        }
    }

    static class Position{
        int r;
        int c;
        int breakingFlag;

        Position(int r, int c, int breakingFlag){
            this.r = r;
            this.c = c;
            this.breakingFlag = breakingFlag;
        }
    }
}