[백준 - 2206] 벽 부수고 이동하기 - Java

문제 설명

 

2206번: 벽 부수고 이동하기

 

접근 방법

해당 문제는 너비 우선 탐색을 이용하여 해결할 수 있었습니다. 2차원 그래프상 특정 지점들간 최단 거리는 보통 너비 우선 탐색을 적용하는데, 깊이 우선 탐색의 경우 말그대로 깊이 탐색하기 때문에 해당 경로가 '최단' 경로인지 구분하기가 어려움 점이 있습니다.

 

일단 벽을 부수는 것을 제외하면 일반적인 너비 우선 탐색 문제입니다. 벽을 하나 부숴야 함으로써 난이도가 꽤나 상승했습니다.

 

벽을 하나 부숴야 하기 때문에 특정 지점에 도달하는 경우의 수는 다음과 같이 4가지로 생각해볼 수 있겠습니다.

 

1. 벽을 한 번도 부수지 않았는데, 벽이 없는 지점(0)에 도착한 경우 → 그냥 지나가면 됨

2. 벽을 한 번도 부수지 않았는데, 벽이 있는 지점(1)에 도착한 경우 → 해당 벽을 부수면 됨

3. 벽을 한 번 부쉈는데, 벽이 없는 지점(0)에 도착한 경우 → 그냥 지나가면 됨

4. 벽을 한 번 부쉈는데, 벽이 있는 지점(1)에 도착한 경우 → 최대 한 번만 부술 수 있으므로 불가!!

 

즉, 기존 너비 우선 탐색을 하면서 위와 같은 조건을 반영해주면 되겠습니다.

 

평상시라면 x, y 좌표와 이동한 거리만을 큐에 저장했겠지만, 벽을 부쉈는지 안부쉈는지를 구분하기 위한 상태값을 하나 더 추가 시켜줍니다.

 

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{1, 1, 1, 0}); // move[3] = 0 : 벽 안 부숨, move[3] = 1 : 벽 부숨

 

아울러, 너비 우선 탐색을 하면서 벽을 한 번 부순 노드와 벽을 한 번도 안부순 노드가 동일한 지점에 방문할 수도 있게되는데, 이 두 노드들은 앞으로 벽을 한 번이라도 더 부술 수 있는지 없는지 차이를 띄기 때문에 서로의 탐색에 영향을 주지 않도록 방문처리를 구분해야할 필요가 있습니다. 그래서 평상시라면 방문 처리용 배열도 2차원 배열이었겠지만, 상태를 구분하기 위해 아래와 같이 3차원 배열을 사용했습니다.

 

    boolean[][][] visited = new boolean[n + 1][m + 1][2];
    
    // ...

    Queue<int[]> queue = new LinkedList<>();
    queue.add(new int[]{1, 1, 1, 0}); // move[3] = 0 : 벽 안 부숨, move[3] = 1 : 벽 부숨
    visited[1][1][0] = true; // 벽을 안 부순 노드가 방문

 

이후 너비 우선 탐색을 진행하는데, 기본적으로 맵의 좌표를 벗어나는 경우와 한 번도 부수지 않은 경우 이미 방문했던 지점을 또 방문하는 경우 그리고 앞서 벽을 한 번이라도 부순 상태에서 이전에 이미 방문했던 지점을 또 방문 하는 경우 그리고 벽을 한 번이라도 부순 상태에서 또 다른 벽을 방문한 경우에 대해선 추가적인 탐색을 하지 않도록 합니다.

 

        int nx, ny;
        while (!queue.isEmpty()) {

            int[] move = queue.poll();

            for (int i = 0; i < 4; i++) {
                nx = move[0] + dx[i];
                ny = move[1] + dy[i];

                if (nx < 1 || nx > n || ny < 1 || ny > m
                    || (move[3] == 0 && visited[nx][ny][0])
                    || (move[3] == 1 && visited[nx][ny][1])
                    || (move[3] == 1 && map[nx][ny] == 1)) {
                    continue;
                }
                
                // ...

 

이후에는 다음 탐색을 위한 조건 등의 작업을 처리해줍니다. 우선 벽을 한 번도 안부쉈는데 벽을 만난 경우에는 해당 벽을 부술 수 있으므로 방문 처리와 함께 이동 거리 + 1 그리고 벽을 부쉈다는 상태를 변경(0 → 1)해줍니다. (아래 코드 참고)

 

                if (map[nx][ny] == 1 && move[3] == 0) {
                    visited[nx][ny][0] = true;
                    queue.add(new int[]{nx, ny, move[2] + 1, move[3] + 1});
                    continue;
                }

 

그 다음으론 벽을 한 번도 안부쉈는데 벽이 없는 지점에 도착한 경우에는 별다른 상태 값 변경 없이 방문 처리와 이동 거리만 + 1 해줍니다. (아래 코드 참고)

 

                else if (map[nx][ny] == 0 && move[3] == 0) {
                    visited[nx][ny][0] = true;
                    queue.add(new int[]{nx, ny, move[2] + 1, move[3]});
                }

 

마지막으로 벽을 한 번 부쉈는데 벽이 없는 지점에 도착한 경우 역시 별다른 상태 값 변경 없이 방문 처리와 이동거리를 + 1 해줍니다. 다만, 방문 처리는 벽이 부순 상태에 대한 방문 처리(visited[nx][ny][1] = true;)를 해주어야 함에 유의해야 합니다. (아래 코드 참고)

 

                else if (map[nx][ny] == 0 && move[3] == 1) {
                    visited[nx][ny][1] = true;
                    queue.add(new int[]{nx, ny, move[2] + 1, move[3]});
                }

 

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {

    static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken());

        boolean[][][] visited = new boolean[n + 1][m + 1][2];
        int[][] map = new int[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            String s = br.readLine();
            for (int j = 1; j <= m; j++) {
                map[i][j] = Integer.parseInt(String.valueOf(s.charAt(j - 1)));
            }
        }

        if (n == 1 && m == 1) {
            System.out.println(1);
            return;
        }

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{1, 1, 1, 0}); // move[3] = 0 : 벽 안 부숨, move[3] = 1 : 벽 부숨
        visited[1][1][0] = true;

        int nx, ny;
        while (!queue.isEmpty()) {

            int[] move = queue.poll();

            for (int i = 0; i < 4; i++) {
                nx = move[0] + dx[i];
                ny = move[1] + dy[i];

                if (nx < 1 || nx > n || ny < 1 || ny > m
                    || (move[3] == 0 && visited[nx][ny][0])
                    || (move[3] == 1 && visited[nx][ny][1])
                    || (move[3] == 1 && map[nx][ny] == 1)) {
                    continue;
                }

                if (nx == n && ny == m) {
                    System.out.println(move[2] + 1);
                    return;
                }

                if (map[nx][ny] == 1 && move[3] == 0) {
                    visited[nx][ny][0] = true;
                    queue.add(new int[]{nx, ny, move[2] + 1, move[3] + 1});
                } else if (map[nx][ny] == 0 && move[3] == 0) {
                    visited[nx][ny][0] = true;
                    queue.add(new int[]{nx, ny, move[2] + 1, move[3]});
                } else if (map[nx][ny] == 0 && move[3] == 1) {
                    visited[nx][ny][1] = true;
                    queue.add(new int[]{nx, ny, move[2] + 1, move[3]});
                }
            }
        }

        System.out.println(-1);
    }
}

 

문제를 풀면서 적용해본 반례

4 3
000
101
101
110

답 : 6

4 3
000
110
111
110

답 : 6

4 3
000
011
001
110

답 : 6

4 4
0001
0111
0101
1100

답 : 7

4 4
0001
0111
0001
1100

답 : 7

4 6
010001
010101
010101
000100

답 : 9

4 7
0110000
0110110
0110110
0000110

답 : 16

4 7
0110000
0110110
0110110
0000010

답 : 10

5 5
00100
11000
00110
01011
00000

답 : 9

6 6
000000
011111
011111
010100
010110
000110

답 : 15

 

참고자료

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