Baekjoon 2178 (미로 탐색)

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

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

using namespace std;

int map[102][102];
int visit[102][102];

// 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 x;
    int y;
    int dist;
};

queue<Coord> q;

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

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

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

        q.pop();

        // check 4 directions
        for(int i = 0; i < 4; i++){
            int next_x = temp.x + direction[i][0];
            int next_y = temp.y + direction[i][1];

            if(map[next_x][next_y] == 1 && next_x >= 0 && next_x < M && next_y >= 0 && next_y < N && visit[next_x][next_y] != 1) {
                // if valid, push node in queue and check 'visited'
                visit[next_x][next_y] = 1;
                q.push( Coord{next_x, next_y, 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[j][i]);
        }
    }

    // bfs (solution)
    bfs();
}

BFS는 최단 거리를 찾을 때 유용하게 사용한다.
(너비 우선 탐색이므로, 가장 빨리 찾아진 solution이 가장 얕은, 즉 최단의 경우이다)

따라서, 미로 탐색에는 BFS를 사용한다.

한 지점에 도달했을 때 다음의 네 방향으로 BFS를 뻗어나갈 때
direction[4][2]의 배열을 사용하여 for문으로 유용하게 처리할 수 있었다. (노가다 줄이기)

각 노드를 Coord 라는 구조체로 정의하고 이로 Queue를 만들어 BFS를 진행하였는데,
이 Coord에는 좌표 정보와 함께 “지금까지 걸린 거리”의 dist 가 있는 것이 포인트이다.

BFS를 진행하면서, dist를 업데이트 해 주며 Queue에 push 하여
Queue에 담긴 모든 노드들이, 얼마의 거리만에 온 노드들인지 확인할 수 있다.