BOJ 2206 - 벽 부수고 이동하기

문제를 읽고 이해하기

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

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

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

입력

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

출력

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

재정의와 추상화

우선 지도에서 특정 위치까지 가는 최단 거리를 구하는 문제이므로, BFS를 이용하여 문제를 풀면 된다. 단, 벽을 한 개 까지 부수고 이동하여도 된다는 조건이 있으므로 이 조건에 유의하여 코드를 짜야한다.

지금까지 BFS를 이용한 최단거리 알고리즘을 풀 때와는 다르게, check 함수를 3차원으로 선언해야 한다. 그 이유는, 벽을 부수고 이동했을 때의 경로와 벽을 부수지 않고 이동했을 때의 경로가 겹칠 경우에 문제가 생기기 때뭉니다.

예를 들어, 벽을 부수고 이동한 경로에서 (2, 4)라는 특정 위치를 통과했다고 치자. 그러면 그 위치에서 check해주는 방문 배열이 true가 된다. 따라서, 벽을 부수지 않고 이동한 경로에서 (2, 4)를 통과할 때 check가 true이므로, 그 위치를 통과할 수 없게 된다. 비록 그 경로가 '최단 경로'여도..

따라서 check[세로위치][가로위치][2]와 같이 3차원 배열로 선언하여, 그 경로가 이미 벽을 부순 적이 있는 경로라면 check[y][x][1]에 기록하고, 그렇지 않은 경로라면 check[y][x][0]에 기록하면 된다.

정리하면 아래와 같다.

• 큐(Queue)에는 Block이라는 구조체 객체가 들어간다.
• Block 구조체는, 현재 위치의
  1. 위치 정보 (y, x)
  2. 벽을 이미 한 번 부순 적이 있는 경로인지 여부 (isBroken)
  3. 현재 위치까지의 거리 (length)
• 현재 위치에서 오른쪽, 왼쪽, 위, 아래 방향으로 1칸 이동한 위치(next_y, next_x)에 대하여
  1. 맵 내부에 있고 (isInside() 함수를 통해 확인)
  2. 한 번도 방문한 적 없는 곳일 때 (!check[next_y][next_x][now.isBroken]
• 그 방향으로 1칸 이동한 위치가 (next_val) 벽(1)이라면 두 가지 선택을 할 수 있다.
  1. 벽을 부수고, 그 방향으로 가는 방법. 이때 isBroken을 true로 만든 Block 객체를 큐에 push한다.
  2. 벽을 이미 부순 적이 있다면(now.isBroken == true), continue;
• 그 방향으로 1칸 이동한 위치가 (next_val) 길(0)이라면
  1. now.isBroken의 값은 유지한 채, 다음 위치에서의 정보와 함께 큐에 push한다.
• check[next_y][next_x][now.isBroken] = true;을 통해 방문 정보를 등록한다.

코드 작성

#include <iostream>
#include <queue>
using namespace std;

int n, m;
int arr[1001][1001];
bool check[1001][1001][2];

typedef struct {
    int y, x;
    bool isBroken;
    int length;
} Block;

typedef struct {
    int y, x;
} Direction;

Direction dir[4] = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };

bool isInside(int y, int x) {
    return y >= 1 && x >= 1 && y <= n && x <= m;
}

int bfs() {
   queue<Block> q;
   q.push({1, 1, false, 1});
   check[1][1][0] = true;

   while (!q.empty()) {
       auto now = q.front();
       q.pop();

       if (now.y == n && now.x == m)
           return now.length;

       for (auto & d : dir) {
           int next_y = now.y + d.y;
           int next_x = now.x + d.x;
           auto & next_val = arr[next_y][next_x];
           if (isInside(next_y, next_x) && !check[next_y][next_x][now.isBroken]) {
               if (next_val) {
                   if (now.isBroken)
                       continue;
                   else {
                       q.push({next_y, next_x, true, now.length + 1});
                   }
               } else
                   q.push({next_y, next_x, now.isBroken, now.length + 1});
               check[next_y][next_x][now.isBroken] = true;
           }
       }
   }
   return -1;
}

int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        string temp;
        cin >> temp;
        for (int j = 0; j < temp.length(); j++)
            arr[i][j + 1] = temp[j] - '0';
    }

    cout << bfs();
    return 0;
}