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

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

 

 

[ 문제 요약 ]

(1, 1)에서 (N, M)까지 벽을 한 개까지 부수고 이동할 수 있을 때 최단 거리를 출력한다. 만약 불가능할 때는 -1을 출력한다.

 

 

[ 문제 풀이 ]

1. 벽을 부섰는지 안 부섰는지 확인하면서 만약 안 부섰다면 벽이 있는 경우에도 벽을 부수고 진행한다.

2. 벽을 부섰다면 가지 않는다.

3. 만약 도착지에 도착하기 전에 큐가 빈다면 갈 수 없다.

 

 

[ 소스 코드 ]

#include <bits/stdc++.h>
using namespace std;

int N, M;
int arr[1010][1010][2];
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };

int BFS(){
    queue<pair<int, pair<int, int>>> q;
    q.push(make_pair(0, make_pair(0, 0)));

    while (!q.empty()){
        int broken = q.front().first;
        int x = q.front().second.first;
        int y = q.front().second.second;
        q.pop();

        if (x == N - 1 && y == M - 1) return arr[x][y][broken] + 1;

        for (int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
            if (arr[nx][ny][0] == 1){
                if (!broken){
                    arr[nx][ny][broken + 1] = arr[x][y][broken] + 1;
                    q.push(make_pair(1, make_pair(nx, ny)));
                }
            }
            else if (arr[nx][ny][0] == 0){
                if (broken == 1 && arr[nx][ny][broken]) continue;
                arr[nx][ny][broken] = arr[x][y][broken] + 1;
                q.push(make_pair(broken, make_pair(nx, ny)));
            }
        }
    }
    return -1;
}

int main() {
    cin >> N >> M;
    for (int i=0; i<N; i++){
        for (int j=0; j<M; j++){
            char ch;
            cin >> ch;
            arr[i][j][0] = ch - '0';
        }
    }
    cout << BFS();
    return 0;
}

 

 

 

[ 주의할 점 ]

BFS의 조건을 잘 설정해주어야 하는 문제였다.