# 백준 : 미로 탐색(2178) - BFS

문제

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

소스

(Github: https://github.com/wonjnlee/wallydev/blob/master/bj_2178_fastestway_BFS)

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <list>
using namespace std;

int map[100][100];
int x_arr[10000], y_arr[10000], cnt_arr[10000];
int cnt, X, Y;

void enqueue(int x_val, int y_val, int cnt_val) {
    x_arr[cnt] = x_val;
    y_arr[cnt] = y_val;
    cnt_arr[cnt] = cnt_val;
    map[y_val][x_val] = 0;
    cnt++;
}

void BFS(int x, int y) {
    int index = 0;
    enqueue(x, y, 1);
    while((index < cnt) && ((x_arr[index] != X - 1) || (y_arr[index] != Y - 1))) {
        //map[y_arr[index]][x_arr[index]] = 0;
        if((y_arr[index] > 0) && map[y_arr[index] - 1][x_arr[index]]) {
            enqueue(x_arr[index], y_arr[index]-1, cnt_arr[index]+1);
        }
        if((y_arr[index] < Y - 1) && map[y_arr[index]+1][x_arr[index]]) {
            enqueue(x_arr[index], y_arr[index]+1, cnt_arr[index]+1);
        }
        if((x_arr[index] > 0) && map[y_arr[index]][x_arr[index]-1]) {
            enqueue(x_arr[index]-1, y_arr[index], cnt_arr[index]+1);
        }
        if((x_arr[index] < X - 1) && map[y_arr[index]][x_arr[index]+1]) {
            enqueue(x_arr[index]+1, y_arr[index], cnt_arr[index]+1);
        }
        index++;
    }
    if(index < cnt) cout<<cnt_arr[index]<<"\n";
}



int main(void) {
    string input;
    cin>>Y>>X;
    for(int i=0; i<Y; i++) {
        cin>>input;
        for(int j=0; j<X; j++) {
            map[i][j] = input.at(j) - 48;
        }
    }
    BFS(0, 0);
    return 0;
}

풀이

지난번 포스팅에서는 DFS를 이용하여 풀었는데, 시간초과가 발생하였다.
해결 방법을 찾던 중, 미로 찾기와 같은 '빠른 길 찾기 류' 문제들은 BFS로 풀어야 한다는 것을 보고, 이를 이용하여 다시 풀어보았다. 
BFS는 기본적으로 '큐(Queue)'를 이용한다. 특정 지점에서 인접한 곳들을 큐로 넣어두고, 하나씩 꺼내면서 확인하는 작업을 반복한다. 처음에 접근 방법을 몰라서 특정 블로그(이 곳)를 참고하였다. 이 분 블로그에서 DFS의 개념과 미로 찾기 코드 또한 공부하였다. 굉장히 대단한 분이라고 생각한다.
어느정도의 개념과 풀이 방식은 이해가 되었는데, 중간에 런타임 오류가 발생하여 해결하는데 시간이 조금 소요되었다. 기존에 내 방식은 방문을 했다는 표시를 한 다음에 큐에 삽입하는 것이었는데, 이를 이용하게 되면 특정한 경우에 오류가 발생한다고 한다. (이 문제에 대한 풀이는 여기를 참고하면 된다)

그래서 기존의 코드에서 큐 방문에 대한 기록을 큐를 삽입하는 부분으로 옮기고 해결하였다.
이 문제는 몇일 뒤에 다시 한번 내 힘으로 풀어봐야할 것 같다...