BOJ 2206번 : 벽 부수고 이동하기

미로에서 최단거리를 찾는 법은 BFS를 사용하면 간단하게 풀리지만, 벽을 뚫고 다닌다면 이야기가 달라진다....

그런데 벽을 또 한번만 뚫을 수 있다고 한다.....

벽을 뚫었을 경우에 대한 플래그를 어떻게 활용을 해야 한다는것은 알겠지만 4방향에서 어느곳을 뚫어야 할지 선택하는것은 불가능 하므로, 모든 경우의 수를 따져봐야 한다. 

그래서 방문체크를 하는 배열에 차원을 더해 플래그를 표시하여 모든 곳에서 플래그를 볼 수 있도록 하였다.

 

또한, 전에 풀었던 문제들의 다른 솔루션을 보았더니 4방향을 체크하는 것을 for문을 사용하여 더욱 짧고 직관적으로 작성하는 방법이 있기에 그것또한 사용하였다. 

세상은 넓고 고수는 많다.... 

 

<Solution>

BFS를 사용하여 최단거리를 찾는 방법은 똑같지만, 벽을 뚫고 왔는지, 아닌지를 판단해야 한다. 이를 위해 방문체크배열을 3차원으로 설정한다. 플래그에 0또는 1로 벽을 뚫오 온 거리인지, 뚫지 않고 온 거리인지 판단할 수 있다.

chk[ y인덱스 ][ x인덱스 ][ 플래그 ] 

예시로 풀어보자.

미로

위의 미로에서 1,1 에서 시작을 하면, 오른쪽과 아래쪽을 뚫어볼 수 있다. 이를 뚫었을때 chk 배열의 flag가 1인 곳에 방문 표시를 해주자. 

왼쪽 처럼 한 칸에서 윗부분은 벽을 뚫지 않고 지나왔을때의 거리,

아래부분은 벽을 뚫고 지나왔을 때의 거리로 생각해보자.

 

방문 체크 배열

이렇게 표시를 하면, 큐에서 뽑아보았을때, 이 노드가 벽을 뚫은적이 있는지 없는지를 판단 할 수 있다. 이 뒤는 조건문에서 판단 가능하게 꾸밀수 있다는 이야기다. 

한번만 더 진행해보면,

(2,1)과 (2,2)는 arr에서 벽이 있는곳(1)인데, 이미 뚫은적이 있다는 사실을 알 수 있으므로, 더이상 진행이 불가능 하고, (1,3)으로는 진행을 할 수 있지만, 전에 벽을 한번 뚫었다는 정보를 표현 할 수 있다.

 

<소스코드>

#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
 
struct map{
    int y, x, f;
};
 
queue<map> q;
 
int arr[1002][1002];
int chk[1002][1002][2] = { 0, };
 
int bfs(int n, int m) {
    int wx[4] = { -1, 0, 1, 0 }; //왼 위 오 아
    int wy[4] = { 0, -1, 0, 1 };
    q.push({ 1,1,0 });
    chk[1][1][0] = 1;
 
    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int f = q.front().f;
        q.pop();
        if (y == n && x == m)
            return chk[y][x][f];
 
        for (int i = 0; i < 4; i++) {
            int nx = x + wx[i];
            int ny = y + wy[i];
 
            if (nx<1 || nx>m || ny<1 || ny>n) // 범위 넘어갈경우 (arr의 주변을 1로 매꾸어도 뚫고 지나가는것 때문에 필요함)
                continue;
            if (chk[ny][nx][f]) // 도착한 경우.
                continue;
            if (!arr[ny][nx]) { // 길(0)이 있는 경우
                chk[ny][nx][f] = chk[y][x][f] + 1;
                q.push({ ny, nx, f });
            }
            if (arr[ny][nx] && !f) { // 벽(1)이 있는경우
                chk[ny][nx][1] = chk[y][x][f] + 1; // 뚫고 지나간 플래그에 넣어줌.
                q.push({ ny, nx, 1 });
            }
        }
    }
    return -1; // 뚫지 못한경우.
}
int main() {
    memset(arr, 1, sizeof(arr));
    int n, m;
    cin >> n >> m;
    getchar();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) 
            arr[i][j] = getchar() - '0';
        getchar();
    }
    cout<<bfs(n, m)<<endl;
}
 
 
 
 
 
 
 
 

 

<문제>

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

2206번: 벽 부수고 이동하기