[Boj 2206] 벽 부수고 이동하기

📎 문제링크

1. 시간복잡도

N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000) 범위가 이와 같이 주어짐에 따라, 각각 벽을 부수는 케이스마다 BFS를 돌리게 되면, O(N^2M^2) = 10^12 → 10000초 로 시간초과가 된다.
따라서, 3차원 배열을 통한 방문처리를 통해 O(NM)의 복잡도로 문제를 해결 할 수 있다.

2. 풀이

2.1 방문처리

3차원 배열을 이용해 벽을 뚫고온 경우 or 그냥 온 경우 정점에 방문하는 경우를 분리해준다.
두 케이스를 분리하지 않고, 2차원 방문배열을 사용하는것이 안되는 반례로 아래의 INPUT을 볼 수 있다.

**INPUT**	**VISIT**
   5 5
  00000		  00000	
  11101		  V0000	
  00001		  V0000	
  01111		  V0000	
  00010		  VVV00
  
  * ANSWER = 15 | OUTPUT = -1
  * (2,1)의 벽을 부순 경우가 (3,1)에 먼저 도착해 방문처리를 하게 된다.
  * BFS는 최단거리를 보장함으로,
    (1,2) -> (1,3) -> (1,4) -> (2,4)...로 돌아 왔을때[=(5,4)의 벽을 부수는 정답 경로]
    (3,1)이 이미 방문처리되어 도달할수 없음(-1)을 출력하게 된다.

2.2 범위체크

항상 범위를 잘봐야한다. N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000) 즉, N==M==1 의 경우가 가능하다.
Queue에 넣기전에 도착여부를 체크하는 방법에서 Queue에서 뺄때 도착여부를 체크하도록 변경해주었다.

**INPUT**
   1 1
   0

* ANSWER = 1 | OUTPUT = -1

3. 유사문제

• 벽 부수고 이동하기 2
• 배달

4. 코드

package week8;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Boj_2206 {
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static int N, M;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] cmd = br.readLine().split(" ");
        N = Integer.parseInt(cmd[0]);
        M = Integer.parseInt(cmd[1]);

        int[][] map = new int[N][M];
        for (int i = 0; i < N; i++) {
            char[] line = br.readLine().toCharArray();
            for (int j = 0; j < M; j++) {
                map[i][j] = line[j] - '0';
            }
        }

        boolean[][][] visit = new boolean[N][M][2];
        Queue<XY> q = new ArrayDeque<>();
        q.add(new XY(0, 0, 1, 0));
        visit[0][0][0] = true;

        int answer = -1;
        while (!q.isEmpty()) {
            XY cur = q.poll();
            
            // 도착
            if (cur.x == N-1 && cur.y == M-1) {
                answer = cur.d;
                break;
            }

            for (int i = 0; i < 4; i++) {
                int tx = cur.x + dx[i];
                int ty = cur.y + dy[i];
                if(isRange(tx, ty)) {
                    // 벽
                    if (map[tx][ty] == 1 && cur.cnt == 0) {
                        if (!visit[tx][ty][cur.cnt+1]) {
                            visit[tx][ty][cur.cnt+1] = true;
                            q.add(new XY(tx, ty, cur.d+1, cur.cnt+1));
                        }

                    }
                    // 벽 아님. 이동
                    else if (map[tx][ty] == 0) {
                        if (!visit[tx][ty][cur.cnt]) {
                            visit[tx][ty][cur.cnt] = true;
                            q.add(new XY(tx, ty, cur.d+1, cur.cnt));
                        }
                    }
                }
            }
        }

        System.out.println(answer);
    }

    static boolean isRange(int x, int y){
        return (x < 0 || y < 0 || x >= N || y >= M) ? false : true;
    }
}

class XY {
    int x;
    int y;
    int d;
    int cnt;

    public XY(int x, int y, int d, int cnt) {
        this.x = x;
        this.y = y;
        this.d = d;
        this.cnt = cnt;
    }
}