[BFS] 넓이 우선 탐색

BFS

BFS란 Breadth First Search의 약자로 넓이 우선 탐색을 의미한다. 주로 다차원의 배열에서 각 칸을 방문하는 경우 사용하는 알고리즘이다. 큐 자료구조와 함께 사용한다.

---

동작 방식

우선 (0,0)의 점을 방문 표시를 한 뒤, 큐에 넣는다. 그 다음 큐가 빌때까지 q.pop() 연산을 하면서 (0,0) 과 인접하면서 방문하지 않은 점을 찾는다. 방문하지 않은 점을 찾으면 그 점을 다시 큐에 넣는다. 다시 q.pop() 연산부터 이를 방복하며, 큐가 비는 순간 종료한다.
이때의 시간복잡도는 O(nm) 이다.

---

코드

#include <iostream>
#include <utility>
#include <algorithm>
#include <queue>

using namespace std;

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    bool vis[100][100] = {false};
    int road[100][100] = {1,0,1,1,1,1,0,0,0,0,1,0,1,1,0};
    queue<pair<int,int>> q;
    q.push({0,0});
    vis[0][0] = 1;
    // 인접하는 점을 찾기 위한 코드
    int xdiv[4] = {1,0,-1,0}; 
    int ydiv[4] = {0,1,0,-1};
    while(!q.empty())
    {
        pair<int,int> cur = q.front(); q.push(cur);
        for(int i =0;i<4;i++)
        {
            int xr = cur.first + xdiv[i];
            int yr = cur.second + ydiv[i];
            if(xr<0||xr>=n||xr<0||yr>=n) continue;
            if(vis[xr][yr] == 1 ||road[xr][yr] ==1) continue;
            q.push({xr,yr});
            vis[xr][yr]= 1;
        }
    }
    
}

주의 사항

• 반드시 (0,0) 혹은 출발점을 방문표시를 하고, 큐에 넣어야한다.
• 방문하고자 하는 점이 0보다 작은지, n보다 크거나 같은지를 검사한 뒤, 방문한 점인지, 1로 표새되어 있는 점인지를 검사해야 런타임에러 를 방지할 수 있다.
• 큐에서 빼낼 때 방문표시를 하면 안된다. 이렇게 되면 똑같은 점 이 큐에 여러번 들어갈 수 있게 되어 오류가 발생할 수 있다. 따라서 반드시 큐에 넣을 때 방문표시를 해야한다.

---