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

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을 출력한다.

예제

입력
6 4
0100
1110
1000
0000
0111
0000

4 4
0111
1111
1111
1110

출력
15

-1

코드

#include<iostream>
#include<queue>
#include<algorithm>
#include<tuple>
#include<algorithm>
#pragma warning(disable:4996)
using namespace std;

int n, m;
int road[1001][1001];
int check[1001][1001][2];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int cnt = 0;
void bfs() {
    check[0][0][0] = 1;
    queue<tuple<int, int, int>> q;
    q.push(make_tuple(0, 0, 0));
    while (!q.empty()) {
        int x, y, z;
        tie(x, y, z) = q.front();
        q.pop();
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx >= 0 && nx <n&&ny >= 0 && ny <m) {
                if (road[nx][ny] == 0 && check[nx][ny][z] == 0) {
                    check[nx][ny][z] = check[x][y][z] + 1;
                    q.push(make_tuple(nx, ny, z));
                }
                if (road[nx][ny] == 1 && z == 0) {
                    check[nx][ny][z + 1] = check[x][y][z] + 1;
                    q.push(make_tuple(nx, ny, z + 1));
                }
            }
        }
    }
}

int main() {
    cin >>n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%1d", &road[i][j]);
        }
    }
    bfs();
    if (check[n - 1][m - 1][0] != 0 && check[n - 1][m - 1][1] != 0) {
        cout << min(check[n - 1][m - 1][0], check[n - 1][m - 1][1]);
    }
    else if (check[n - 1][m - 1][0] != 0) {
        cout << check[n - 1][m - 1][0];
    }
    else if (check[n - 1][m - 1][1] != 0) {
        cout << check[n - 1][m - 1][1];
    }
    else {
        cout << -1;
    }
    cout << "\n";
    return 0;
}

해결방법

• 알고스팟문제는 목적지까지 도달하기 위해 부순 벽의 개수를 구했었지만 이번 문제에서는 오직 한 번만 없앨 수 있으며, 없애지 않고도 최단거리로 도달할 수 있는 경우 그 값이 답이된다.

    int check[1001][1001][2];

• x좌표, y좌표 ,벽을 부수지 않고 이동한경우 & 부수고 이동한 경우를 나타낸다. 즉 check[n][m][0]인경우 부수지 않고 이동한 경우이며 , check[n][m][1]인경우 부수고 이동한 경우에 대한 해당 좌표까지의 이동횟수를 저장하게 된다.

• 세 가지 인자값을 한번에 받아서 queue에 넣기 위해 tuple를 사용하였다.

  • tuple의 값을 순서대로 변수에 저장하려면 tie()를 사용한다.

    if (nx >= 0 && nx <n && ny >= 0 && ny <m) {
      if (road[nx][ny] == 0 && check[nx][ny][z] == 0) {
          check[nx][ny][z] = check[x][y][z] + 1;
          q.push(make_tuple(nx, ny, z));
      }
      if (road[nx][ny] == 1 && z == 0) {
          check[nx][ny][z + 1] = check[x][y][z] + 1;
          q.push(make_tuple(nx, ny, z + 1));
      }
    }

• 최단거리를 찾기위해 여태 우리가 BFS탐색을 했을 때에는 길이 존재하며, 방문의 유무만 확인했으면 찾을 수 있었다. 하지만 이번 문제에서는 여러가지 경우의 수가 발생한다.

  1. 벽을 부수지 않고 이동하였을 때 최단거리가 나오는 경우.
  2. 벽을 부수고 이동해여 최단거리가 나오는 경우.
  3. 벽을 부수고 이동해야먼 목적지에 도착이 가능한 경우.
  4. 목적지에 도달할 수 없는 경우.

• 네가지의 경우들을 고려하여 BFS를 작성한다.

1. 처음으로 벽이 아닐 때 방문한 적이 없다면, 현재 경로에 이전 경로까지 걸린 거리 +1을 해주면 된다.

2. 만약 벽이 존재하고 , 벽을 부순적이 없을 때, 즉 z값이 0인 경우에는 check[n][m][z+1]에 이전 경로까지 걸린 거리 +1을 해준다. 여기서 check[n][m][0]은 벽을 부수지 않고 이동한 경우에 대한 경로이기 때문에 꼭 z+1을 해준다. 여기서 q에 데이터를 넣어줄 때 nx,ny,z가아닌 nx,ny,z+1을 넣어줌으로서 벽을 부수고 이동한 것에 표시해줘야한다.

```
if (check[n - 1][m - 1][0] != 0 && check[n - 1][m - 1][1] != 0) {
    cout << min(check[n - 1][m - 1][0], check[n - 1][m - 1][1]);
}
else if (check[n - 1][m - 1][0] != 0) {
    cout << check[n - 1][m - 1][0];
}
else if (check[n - 1][m - 1][1] != 0) {
    cout << check[n - 1][m - 1][1];
}
else {
    cout << -1;
}
```

• 마지막으로 최단거리를 출력할 때 마찬가지로 네가지의 경우의 수를 고려한다.
  1. 벽을 부수지 않았거나, 벽을 부수고 이동해서 목적지에 도달한경우.
     • 두 경우의 값에 대해서 최소 값을 출력해준다.
  2. 벽을 부수지 않고 이동하여 목적지에 도달한경우.
  3. 벽을 부수고 이동하여 목적지에 도달한경우.
  4. 목적지에 도달하지 못한 경우.