[백준] 2206번: 벽 부수고 이동하기 (Java)

1. 문제설명

NxM의 행렬로 표현되는 맵에서 0은 이동할 수 있는 곳, 1은 이동할 수 없는 곳을 나타낸다. (1, 1)에서 (N, M)까지 이동할 때 최단 경로로 이동하려 한다. 만약 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 더 짧은 경로가 된다면, 벽을 한 개까지 부수는 것이 허용된다.

주어진 맵에서 최단 경로를 구하는 문제이다.

• 시간 제한: 2초
• 메모리 제한: 192MB

 

2. 접근 방식

⇒ 최단 거리를 찾는 문제이기 때문에 BFS 문제이지만, 벽을 한 번 부수는 것을 허용하는 조건 때문에 한 번의 BFS로 해결할 수 없다.

• 각 위치에서 벽을 부수지 않은 상태와 벽을 부순 상태를 모두 고려해야 한다.
  • `visited[i][j][0]`: (x, y) 위치에 벽을 부수지 않은 상태로 방문했는지
  • `visited[i][j][1]`: (x, y) 위치에 벽을 부순 상태로 방문했는지
• BFS에서 벽을 부수지 않고 이동할 수 있는 경우와 벽을 부수고 이동할 수 있는 경우를 각각 탐색한다.
• 이동할 수 있는 곳일 때 (`map[nx][ny] == 0`)
  • 아직 방문하지 않은 경우(`visited[nx][ny][z] == 0`), 현재 상태 그대로 이동한다.
  • 이동 후의 상태는 여전히 `z`로 유지되며, `visited[nx][ny][z]`에 현재 거리 + 1을 저장한다.
• 벽이 있는 경우 (`map[nx][ny] == 1`)
  • 벽을 부술 수 있는 상태(`z == 0`)에서만 벽을 부수고 이동할 수 있다.
  • 벽을 부순 후에는 상태가 `z = 1`로 변경되며, `visited[nx][ny][1]`에 거리 + 1을 저장한다.
  • 이 상태에서는 이후 모든 경로 탐색에서 `z=1`을 유지한다.
• 목표 지점에 도달하면 최단 거리를 저장하고, 도달하지 못하면 -1을 저장한다.

 

3. 틀린 이유

벽을 하나씩 깨고 이동하는 모든 경우를 탐색하는 DFS 방법을 사용했더니 “시간초과”가 발생했다.

 

기존 코드

static void dfs(int x, int y, boolean breakWall, int dis) {
    if(x==n && y==m) { // 목표지점까지 도달하면
        minDis = minDis > dis ? dis : minDis; // 최단 거리 갱신
        return;
    }

    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]) {
                visited[nx][ny] = true;
                dfs(nx, ny, breakWall, dis+1);
                visited[nx][ny] = false;
            }
            if(!breakWall && map[nx][ny] == 1 && !visited[nx][ny]) {
                map[nx][ny] = 0;
                visited[nx][ny] = true;
                dfs(nx, ny, true, dis+1);
                map[nx][ny] = 1;
                visited[nx][ny] = false;
            }
        }
    }
}

 

⇒ BFS를 이용해야 한다.

 

4. 최종 코드

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

public class Main {
    static int n, m; // 행, 열 개수
    static int[][] map; // 맵 정보 저장
    static int[][][] visited; // 최단 거리 저장
    static int minDis = Integer.MAX_VALUE; // 최단 거리 저장

    // 상하좌우
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    static void bfs() {
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{1, 1, 0}); // (1, 1)에서 벽을 부수지 않은 상태(0)로 시작
        visited[1][1][0] = 1; // (1, 1) 방문 처리 및 거리 1로 초기화

        while (!q.isEmpty()) {
            int[] c = q.poll(); // 현재 위치와 벽 부순 상태를 가져옴
            int x = c[0], y = c[1], z = c[2];

            if(x==n && y==m) { // 목표지점에 도달한 경우
                minDis = visited[x][y][z]; // 목표지점까지의 최단 거리 저장
                return;
            }

            for(int i=0; i<4; i++) {
                int nx = c[0] + dx[i];
                int ny = c[1] + dy[i];
                if(nx>0 && nx<=n && ny>0 && ny<=m) { // 맵의 범위 내에 있을 경우
                    // 다음 위치가 벽이 아니고, 아직 방문하지 않은 경우
                    if(map[nx][ny]==0 && visited[nx][ny][z]==0) {
                        // 벽을 부수지 않은 상태(z=0) 또는 부순 상태(z=1)에서 
                        // 방문하지 않은 곳이라면 해당 위치까지의 거리를 갱신하고 큐에 추가
                        visited[nx][ny][z] = visited[x][y][z] + 1; // 거리 저장
                        q.add(new int[]{nx, ny, z});
                    }
                    // 다음 위치가 벽이고, 아직 벽을 부순 적이 없는 경우
                    if(map[nx][ny]==1 && z==0 && visited[nx][ny][1]==0) {
                        // 현재까지 벽을 부수지 않은 상태(z=0)에서
                        // 벽을 부수고 그 위치로 이동하는 경우를 처리
                        // 벽은 부순 상태(z=1)로 해당 위치까지의 거리를 갱신하고 큐에 추가
                        visited[nx][ny][1] = visited[x][y][z] + 1;
                        q.add(new int[]{nx, ny, 1});
                    }
                }

            }
        }

        minDis = -1;
        return;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input1 = br.readLine().split(" ");
        n = Integer.parseInt(input1[0]);
        m = Integer.parseInt(input1[1]);
        map = new int[n+1][m+1];
        visited = new int[n+1][m+1][2];
        for(int i=1; i<=n; i++) {
            String input2 = br.readLine();
            for(int j=1; j<=m; j++) {
                map[i][j] = input2.charAt(j-1) - '0';
            }
        }

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

 

5. 추가

그럼 만약 벽을 부술 수 있는 횟수가 K로 주어진다면, 어떻게 수정해야할지 궁금해졌다.

상태를 관리하기 위한 `z`를 0과 1로 구분하는 대신, 벽을 몇 번 부쉈는지를 나타내는 값으로 확장해야 한다.

즉, `z`가 0부터 K까지의 값을 가질 수 있다.

그리고 벽을 만났을 때의 처리도 바뀌어야 한다. `z`가 K보다 작은 경우에만 벽을 부수고 이동할 수 있도록 변경해야 한다.

아래는 생각한대로 변경한 코드이다.

if (nx > 0 && nx <= n && ny > 0 && ny <= m) { // 맵의 범위 내에 있을 경우
    // 벽이 없는 경우
    if (map[nx][ny] == 0 && visited[nx][ny][z] == 0) {
        visited[nx][ny][z] = visited[x][y][z] + 1; // 거리 저장
        q.add(new int[]{nx, ny, z}); // 상태 유지하고 큐에 추가
    }
    // 벽이 있는 경우, 벽을 부술 수 있는 횟수가 남아있다면
    if (map[nx][ny] == 1 && z < k && visited[nx][ny][z + 1] == 0) {
        visited[nx][ny][z + 1] = visited[x][y][z] + 1; // 벽을 부수고 이동
        q.add(new int[]{nx, ny, z + 1}); // 벽을 부순 상태로 큐에 추가
    }
}

 

6. 느낀점 or 기억할정보

처음에 DFS로 설계하면서 실력이 좀 늘었나 생각했는데, DFS로 풀면 시간초과가 발생하는 것을 보고 실망헀다...

그래도 `visited`배열을 3차원 배열로 생성해서 해결할 수 있는 방법을 이해한 시간이 된 것 같아서 나쁘지 않다. 

다음에 비슷한 문제가 나오면 한 번에 풀 수 있기를..