백준 문제

백준 2206 (벽 부수고 이동하기) c++

kangyuseok 2022. 2. 25. 15:39
728x90

문제

 

2206번: 벽 부수고 이동하기

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로

www.acmicpc.net

행렬의 크기 nm이 주어지면 1이면 벽이고 0이면 갈 수 있는 길입니다.

이때 벽을 한번 부수고 통과할 수 있다고 할때 최단거리를 구하는 문제입니다.

 

최단 거리이므로 BFS로 이용하면 됩니다.

 

원래 평소대로라면 bool visited[x][y] : arr[x][y]에 해당하는 부분을 방문하면 true로 바꿔주었지만

벽을 부수는 경우도 생각해줘야 하기때문에 방문기록이 총 3차원으로 생각할 수 있습니다.

int dist[x][y][0] : 벽을 하나도 안부수고 arr[x][y]까지 도달할 동안 최단거리

int dist[x][y][1] : 벽을 한번 부수고 arr[x][y]까지 도달할 동안 최단거리

즉 약간 dp처럼 생각해주면 됩니다.

1번째 줄 cnt는 마지막에 최단거리를 저장하기 위한 변수입니다.   

2번째 줄 end는 탐색을 완료가능한지 체크하기 위한 변수입니다.

end가 true이면 끝까지 탐색가능하므로 cnt를 출력해주고

end가 false이면 탐색 불가능하므로 -1을 출력해주면 됩니다.

3번째 줄을 보면 bfs 부분의 큐 부분을 tuple로 받아주었습니다.

{x, y, 지금까지 벽을 부순 횟수}

10번째 줄은 탐색이 완료되었으므로 최단거리를 cnt에 저장하는 

부분 입니다.

 

 

이제 상하좌우로 돌아가면서 벽을 부수고 이동가능한지 그냥 이동하는지 확인해줄것입니다.

먼저 조건이 존재합니다.

1) 당연히 다음에 갈 위치가 0보다 작으면 안되고 n이나 m보다 크거나 같으면 안됩니다.

2) dist[nx][ny][check] 가 값이 들어있으면 이전에 방문했다는 증거이므로 continue를 해야합니다.

 

3) arr[nx][ny]가 0이고 check가 0이면 dist[nx][ny][0] = dist[x][y][0] +1 입니다.

4) arr[nx][ny]가 0이고 check가 1이면 dist[nx][ny][1] = dist[x][y][1] + 1 입니다. 

벽을 한번 부쉈기 때문에 부순 상태에서만 생각해줘야 합니다.

5) arr[nx][ny] = 1 이고 check가 0이면 이전에 벽을 부순적이 없으므로

벽을 부술 수 있습니다.

따라서 dist[nx][ny][1] = dist[x][y][0] + 1 입니다.

전체 코드입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<cmath>
#include<map>
#include<set>
#include<tuple>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int on[4] = { 0, 1, 0, -1 };
int off[4] = { 1, 0, -1, 0 };
int arr[1001][1001];
int dist[1001][1001][2];
string st;
int n, m;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> st;
        for (int j = 0; j < m; j++) {
            arr[i][j] = st[j] - '0';
        }
    }
    int cnt;
    bool end = false;
    queue<tuple<int, int, int>>q;
    q.push({ 0, 0, 0 });
    dist[0][0][0] = 1;
    while (!q.empty()) {
        int x = get<0>(q.front());
        int y = get<1>(q.front());
        int check = get<2>(q.front());
        if (x == n - 1 && y == m - 1) {
            cnt = dist[x][y][check];
            end = true;
            break;
        }
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + on[i];
            int ny = y + off[i];
            if (dist[nx][ny][check])continue;
            if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
                if (!arr[nx][ny] && check ==0) {
                    dist[nx][ny][0] = dist[x][y][0] + 1;
                    q.push({ nx, ny,0 });
                }
                else if (arr[nx][ny] == 1 && check == 0) {
                    dist[nx][ny][1] = dist[x][y][0] + 1;
                    q.push({ nx, ny, 1 });
                }
                else if (!arr[nx][ny] && check == 1) {
                    dist[nx][ny][1] = dist[x][y][1] + 1;
                    q.push({ nx, ny, 1 });
                }
            }
        }
    }
    if (end)
        cout << cnt;
    else cout << -1;
 
    return 0;
}
 
cs