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

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

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

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

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

---

 늘 사용하던 BFS로는 풀 수 없는 문제이다. 지금까지 BFS를 사용하여 풀었을 때는 지나온 곳을 check하면서 재방문을 안하는 방식으로 풀었다. 하지만 이번엔 벽을 부순다는 옵션이 들어가서 테스트케이스가 다음과 같이 나오는 경우 문제가 발생한다.

 

6 7
0111111
0110000
0110110
0110110
0010111
0000110

 

위의 경우에서 벽을 안부수고 0만 지나오는 경로보다 빨간색 1을 부수고 가는 것이 더 빠르기 때문에 도착지까지의 길은 빨간색 1을 부수고 지나가는 방법에의해 미리 방문이 돼서 재방문이 불가능하다. 만약 빨간색 1을 부수고 지나가는 것이 최단거리일 경우에는 상관없지만 이 방법은 목적지 앞의 초록색 1을 부수지 못해 끝에 도달하지 못한다. 따라서 가장 선두로 경로탐색에 나서던 빨간색 1을 경유하는 경로가 막히면서 뒤에 나머지 경우의 수조차 막히게 된다.

 따라서 우리는 재방문의 방법을 다시 생각해야할 필요가 있다. 위의 경우처럼 벽을 부수고 지나간 경로를 벽을 부수지 않은 경우가 지나갈 수 있게 해야하는 것이다.  따라서 check라는boolean형 2차원배열을 3차원으로 바꿔 벽을 부순경우와 벽을 안부순 경우의 방문처리를 따로 처리를 할 것이다.

 그리고 벽을 부쉈는지의 여부와 현재까지의 거리를 합산한 값은 Now 라는 클래스에 저장해 확인 할 수 있게 할 것이다.

 

그러면 전체적인 구현방법은 설명을 했으니 코드를 보고 이해해보자.

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

class Now{
    int i;
    int j;
    int dis;
    boolean broken_wall;
    Now(int i, int j,int dis, boolean broken_wall)
    {
        this.i = i;
        this.j = j;
        this.dis = dis;
        this.broken_wall = broken_wall;
    }

}
class Main {
    static int[] di = {0, 1, 0, -1};
    static int[] dj = {1, 0, -1, 0};
    static int n;
    static int m;
    static int ans = -1;

    static void bfs(int[][] map)
    {
        // check[][][0] : 벽을 부수지 않은 경우 방문 처리
        // check[][][1] : 벽을 부순 경우 방문 처리
        boolean[][][] check = new boolean[n][m][2];
        Queue<Now> q = new LinkedList<>();
        // 첫번째 방문지 세팅
        q.add(new Now(0, 0, 1,false));
        check[0][0][0] = true;

        while (!q.isEmpty())
        {
            // 현재 방문지의 위치
            Now now = q.poll();
            int i = now.i;
            int j = now.j;
            // 만약 현재 방문지가 도착지면 ans 저장하고 탈출
            if (i == n - 1 && j == m - 1)
            {
               ans = now.dis;
               break;
            }
            // 현재 방문지 상하좌우를 방문
            for (int k = 0; k < 4; k++)
            {
                int i2 = i + di[k];
                int j2 = j + dj[k];
                // 인접한 곳이 index 범위내인 경우
                if (i2 >= 0 && i2 < n && j2 < m && j2 >= 0)
                {
                    // 만약 인접한 곳이 벽이 아닌 경우
                    if (map[i2][j2] == 0)
                    {
                        // 만약 벽을 부순적이 있고 지나간 적이 없는 경우
                        if (now.broken_wall && !check[i2][j2][1])
                        {
                            // 방문처리 후 거리값 +1 해주고 큐에 넣기
                            check[i2][j2][1] = true;
                            q.add(new Now(i2, j2, now.dis + 1, true));
                        }
                        // 만약 벽을 부순적이 없고 지나간 적이 없는 경우
                        else if (!now.broken_wall && !check[i2][j2][0])
                        {
                            // 방문처리 후 거리값 +1 해주고 큐에 넣기
                            check[i2][j2][0] = true;
                           q.add(new Now(i2, j2, now.dis + 1, false));
                        }
                    }
                    // 만약 인접한 곳이 벽인 경우
                    else {
                        // 만약 벽을 부순적이 없고 지나간 적이 없는 경우
                        if (!now.broken_wall && !check[i2][j2][0])
                        {
                            // 방문처리 후 거리 +1 해주고 벽을 부쉈다는 표시하고 큐에 넣기
                            check[i2][j2][0] = true;
                            q.add(new Now(i2, j2, now.dis + 1, true));
                        }
                    } 
                }
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        int[][] map = new int[n][m];
        for (int i = 0; i < n; i++)
        {
            String s = br.readLine();
            for (int j = 0; j < m; j++)
                map[i][j] = s.charAt(j) - '0';
        }
        bfs(map);
        // ans = -1로 시작하기 때문에 방문하지 못하면 -1이고
        // 방문한 경우 값이 바뀌어서 나옴
        System.out.println(ans);
    }
}

 위와 같은 방법으로 풀면 어려움 없이 해결할 수 있는 문제이다.

 

 내가 많이 해멘이유는 2가지였다.

1. 방문처리를 1개로 풀려고 한것.

2. 지나온 거리를 저장하는 배열을 만들어서 해결하려한 것.

 

우선 1번은 위에서 언급했으니 넘어가고 1번을 처리하고나서도 '틀렸습니다'라는 결과가 나와 고민을 많이 했다.

그 이유를 찾은 부분이 2번이었다. 배열로 만들어 값을 저장하면 큐에서 대기할때 갖고있던 거리값이 큐에서 먼저 나온 다른 요소에 의해 큐에서 나오기 전에 바뀔 수 있다는 점이었다. 즉 쉽게 말하면 큐에 들어갈때 거리의 값과 나올때의 거리의 값이 달라질 수 있다는 것이다. 그래서 class Now에 거리값을 추가해 이 부분을 처리했더니 마지막 오류를 고칠 수 있었다.

 

 그냥 BFS로 쉽게 풀 수 있는 문제라 생각하고 방심했지만 굉장히 배울점과 생각할 점이 많은 문제였다. 개념을 하나 알았다고 자만하지 말고 응용할 수 있는 능력을 길러야겠다.