[Gold-3] 2206번 | BFS | 자바(Java)

https://www.acmicpc.net/problem/2206

 

입력

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

출력

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

 

해당 백준 문제는 BFS를 심화한 문제로, NxM의 숫자 맵에 1이 존재할 경우(벽이 존재할 경우), 이 벽을 허물 수 있다는 경우의 수까지 포함하여 최단 거리를 구하는 문제이다. 단, 벽은 한번만 허물 수 있다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

 

우선, 기존의 BFS 최단거리 문제 틀에서 크게 벗어나지 않은 채로

해당 벽을 허물었는가, 허물지 않았는가에 대한 정보만 담으면 문제는 쉽게 풀이할 수 있다.

 

static int bfs() {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0, 0, 0}); // 시작점 {x, y, 벽 부숨 여부}
        visited[0][0][0] = 1; // 시작점 방문 처리 (거리 1)

        while (!q.isEmpty()) {
            int[] current = q.poll();
            int x = current[0];
            int y = current[1];
            int wallBroken = current[2];

            // 목표 지점 도달
            if (x == N - 1 && y == M - 1) {
                return visited[x][y][wallBroken];
            }

            // 상하좌우 이동
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                // 맵 범위 내에 있는지 확인
                if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
                    // 벽이 아닌 경우
                    if (map[nx][ny] == 0 && visited[nx][ny][wallBroken] == 0) {
                        visited[nx][ny][wallBroken] = visited[x][y][wallBroken] + 1;
                        q.add(new int[]{nx, ny, wallBroken});
                    }

                    // 벽이고, 아직 벽을 부수지 않은 경우
                    if (map[nx][ny] == 1 && wallBroken == 0 && visited[nx][ny][1] == 0) {
                        visited[nx][ny][1] = visited[x][y][wallBroken] + 1;
                        q.add(new int[]{nx, ny, 1});
                    }
                }
            }
        }

        return -1; // 도달 불가한 경우
    }

 

여기서 맵 범위 내에 벽이 아닌 경우과 벽인 경우 두 가지를 나눠서 생각해보자.

탐색 과정은 지금까지 했던 BFS와 같이 상하좌우로 이동 가능한 좌표로 탐색한다. 그리고 (N,M)에 도달한 경우에는 거리 값을 반환하면 된다. (그렇지 못할 경우는 -1 반환)

 

만약, 맵에서 0인 부분 즉, 벽이 아닌 부분을 탐색하는 경우엔 최단 거리를 구하기 위해 그저 visited + 1만 하면 된다.

 

참고로 여기서 visited는 int 형 3차원 배열로 가로, 세로, 벽 부숨의 여부로

visited[x][y][0]은 벽을 부수지 않고 (x, y)에 도달한 경우, visited[x][y][1]은 벽을 부수고 도달한 경우를 의미한다.

 

 

그러나 맵에서 1인 부분 즉, 벽인 경우에는 이 벽을 허물 수 있다는 경우의 수를 반영해야한다.

if (map[nx][ny] == 1 && wallBroken == 0 && visited[nx][ny][1] == 0)

 

해당 코드를 보면 의미 파악이 쉬울 텐데

1) map에서 숫자가 1이고

2) 현재까지 벽을 부순 적이 없었으며 (이미 부서진 벽이라면 해당 x)

3) 벽을 부수고 나서 nx, ny에 도달했는지 (벽을 부수고 이동한 적이 없을 때)

 

위 세 가지 조건을 통해 중복 방문을 방지하고

visited[nx][ny][1] = visited[x][y][wallBroken] + 1;
q.add(new int[]{nx, ny, 1});

 

현재 위치 (x,y)에서 (nx,ny)로 이동한 거리 값을 갱신한다.

그리고 여기서 wallBroken은 이제 한번 부셨으므로 wallBroken 값이 1이되어 추가적인 벽을 부수는 동작이 제한된다.

 

---

시간 복잡도

• 노드 수: 최대 N×M×2 (벽 부순 여부에 따른 상태 구분)
• 시간 복잡도: O(N×M) (BFS 탐색)