Baekjoon 2206 (벽 부수고 이동하기)

Baekjoon 2206, 백준 2206 문제의 본인 풀이입니다!
문제는 아래의 링크에서 확인할 수 있습니다.
문제보기

#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

int map[1002][1002];
int visit[1002][1002];  // 0: not visited, 1: usedWall = false, -1: usedWall = true

// to check 4 directions by 'for' loop
int direction[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int N, M;

typedef struct Coord {
    int i;
    int j;
    bool usedWall;
    int dist;
};

queue<Coord> q;

bool canArrive = false;

void bfs(){
    // use queue
    // start from (0,0)
    visit[0][0] = 1;
    q.push( Coord{0,0,false,1} );

    // bfs until arrival
    while(!q.empty()){
        // visit front node of q
        Coord temp = q.front();

        // if arrived final destination
        if(temp.i == N-1 && temp.j == M-1){
            canArrive = true;
            printf("%d\n", temp.dist);
            break;
        }

        q.pop();

        // better case exist (not using breakWall) : delete
        if(temp.usedWall && visit[temp.i][temp.j] == 1) continue;

        // check 4 directions
        for(int i = 0; i < 4; i++){
            int next_i = temp.i + direction[i][0];
            int next_j = temp.j + direction[i][1];

            if(next_i >= 0 && next_i < N && next_j >= 0 && next_j < M) {
                // not breaking wall
                if(map[next_i][next_j] == 0) {
                    // if valid, push node in queue and check 'visited'
                    // not used breakWall
                    if(!temp.usedWall && visit[next_i][next_j] != 1) {
                        visit[next_i][next_j] = visit[temp.i][temp.j];
                        q.push( Coord{next_i, next_j, temp.usedWall, temp.dist + 1} );
                    }

                    // used breakWall
                    else if(temp.usedWall && visit[next_i][next_j] == 0) {
                        visit[next_i][next_j] = visit[temp.i][temp.j];
                        q.push( Coord{next_i, next_j, temp.usedWall, temp.dist + 1} );
                    }
                }

                // breaking wall
                if(map[next_i][next_j] == 1 && !temp.usedWall && visit[next_i][next_j] == 0) {
                    visit[next_i][next_j] = -1;
                    q.push( Coord{next_i, next_j, true, temp.dist + 1} );
                }
            }
        }
    }
}

int main() {
    // put inputs
    scanf("%d %d", &N, &M);

    // initialization
    memset(visit, 0, sizeof(visit));
    memset(map, 0, sizeof(map));

    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            scanf("%1d", &map[i][j]);
        }
    }

    // bfs (solution)
    bfs();

    if(!canArrive) printf("-1\n");
}

기존에 비해 고려할 것이 추가되었던 BFS 미로찾기 문제였다.

우선, 각 노드에 도착했을 때 기존에 ‘벽 부수기’를 썼는지, 쓰지 않았는지를 구별해야 했다.
벽 부수기를 쓰고 더 먼저 도착한 노드와, 벽 부수기를 쓰지 않고 더 늦게 도착한 노드가
본 문제에서는 모두 고려 대상이기 때문이다.

필자는 visit 함수에 변화를 주어, 기존 0(방문X) / 1(방문) 에서 -1 을 추가하여 각 노드를 세 가지 상태로 두었다.

이를 위해 기존 i 좌표, j 좌표, dist (거리) 의 세 가지 변수가 담기는 Coord에 bool 형태의 usedWall 을 추가하여, ‘벽 부수기’의 사용 여부를 가렸다.

이후에는 침착하게 경우 나누면서 BFS 진행하면 된다.