벽 부수고 이동하기

1. 문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.
만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.
한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.
맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

---

입력

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

---

출력

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

---

예제 입력 1

6 4
0100
1110
1000
0000
0111
0000

예제 출력 1

15

---

2. 문제 판단

BFS 사용 진단

1. 최단 거리(최단 경로, 가장 적은 칸 수 등) 키워드는 BFS 신호!!!

이 문제는 BFS(Breadth-First Search)를 활용하되,
벽을 한 번 부술 수 있는 상태를 고려하여 탐색해야 하는 상태 확장형 최단 경로 문제
즉, 모든 이동 비용이 동일한 상황에서의 최단 거리 → BFS가 정답

• DFS는 깊이 우선이기에 최단 거리 보장을 못 함
• 이동에 가중치가 있다면 Dijkstra

2. 2차원 맵 탐색 구조

맵이 N x M 행렬로 주어지고, 인접 칸(상하좌우)으로만 이동 가능하다고 했을 때 → 전형적인 2D Grid 탐색 문제.

3. 벽을 딱 1번 부술 수 있음 → 상태 추가 BFS

다음 유형과 비슷함

• 말이 체스판에서 이동하는 Knight 문제에서 점프 횟수 제한이 있는 경우
• 포탈을 한 번만 사용할 수 있는 미로 탈출 문제
• K번 점프할 수 있는 미로 문제
• 하지만 언제 상태값이 변했는지 고려 안됨
  • 앞서 상태가 변경되면 이후는 고려하지 않아 반영된 최단거리가 최적의 최단 거리인지 판단이 되지 않음
  • 보완을 위해 BFS + DP 적용

4. 탐색의 결과가 항상 최소 보장됨. > BFS의 특징: 먼저 도달한 경로가 항상 가장 짧은 경로

따라서 (N-1, M-1)에 처음 도달하는 순간의 거리가 최단 거리임을 보장 가능

---

3. 구현

static int N, M;  
static int[][] map;  
static int[][][] dp;  
static int[] dx = {-1, 1, 0, 0};  
static int[] dy = {0, 0, -1, 1};

public static void main(String[] args) {  
    Scanner sc = new Scanner(System.in);  
    N = sc.nextInt();  
    M = sc.nextInt();  
    map = new int[N][M];  
    for (int i = 0; i < N; i++) {  
        String line = sc.next();  
        for (int j = 0; j < M; j++) {  
            map[i][j] = line.charAt(j) - '0';  
        }  
    }  
    System.out.println(bfsWithDP());  

} 

static class State {  
    int x, y, dist, broken;  

    public State(int x, int y, int dist, int broken) {  
        this.x = x;  
        this.y = y;  
        this.dist = dist;  
        this.broken = broken;  
    }  

    State move(int dx, int dy) {  
        return new State(x + dx, y + dy, dist + 1, broken);  
    }  

    State breakWall(){  
        return new State(x, y, dist, broken + 1);  
    }  

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

}  

static int bfsWithDP(){  
    Queue<State> queue = new LinkedList<>();  
    dp = new int[N][M][2];  
    for(int i = 0; i < N; i++){  
        for(int j = 0; j < M; j++){  
            dp[i][j][0] = Integer.MAX_VALUE;  
            dp[i][j][1] = Integer.MAX_VALUE;  
        }  
    }  

    queue.offer(new State(0, 0, 1, 0));  
    dp[0][0][0] = 1;  
    while(!queue.isEmpty()){  
        State cur = queue.poll();  
        if(cur.x == N - 1 && cur.y == M - 1){  
            return cur.dist;  
        }  
        for(int d = 0; d < 4; d++){  
            State next = cur.move(dx[d], dy[d]);  
            if(!next.inBounds(N, M)) continue;  
            if(map[next.x][next.y] == 0 && dp[next.x][next.y][cur.broken] > next.dist){  
                dp[next.x][next.y][cur.broken] = next.dist;  
                queue.offer(next);  
            }else if(map[next.x][next.y] == 1 && cur.broken == 0 && dp[next.x][next.y][1] > next.dist){  
                dp[next.x][next.y][1] = next.dist;  
                queue.offer(next.breakWall());  
            }  
        }  
    }  
    return -1;  
}