너비 우선 탐색(BFS)

💡 너비 우선 탐색(BFS, Breath-First-Search)란?

루트 노드(or 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

• 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.
• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
• 두 노드 사이의 최단 경로 또는 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
  ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현. A와 B사이에 존재하는 경로를 찾는 경우
  → 깊이 우선 탐색(DFS): 모든 친구 관계 탐색
  → 너비 우선 탐색(BFS): A와 가까운 관계부터 탐색
• 너비 우선 탐색(BFS)이 깊이 우선 탐색(DFS)보다 복잡하다.

✔️ 너비 우선 탐색(BFS) 특징

• 방문한 노드들을 차례로 저장한 후, 꺼낼 수 있는 자료구조인 큐(Queue)를 사용한다.

  → 선입선출(FIFO) 원칙으로 탐색한다.

• 직관적이지 않다. 시작 노드에서 시작해서 거리에 따라 단계별로 탐색한다.

• 재귀적으로 동작하지 않는다.

• ‘Prim’, ‘Dijkstra’ 알고리즘과 유사하다.

• 그래프 탐색의 경우, 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다.
  (방문 여부를 검사하지 않을 경우 무한 루프에 빠질 위험이 있다.)
  
  

✔️ 너비 우선 탐색(BFS) 과정

1. A노드(시작 노드) 방문한다.
   → queue에 방문한 노드를 삽입한다.[enqueue]
   → 초기 상태의 queue에는 시작 노드만이 저장되어있다.
   ⇒ A노드의 이웃 노드를 모두 방문한 다음에 이웃의 이웃들을 방문한다.
2. queue에서 꺼낸 노드와 인접한 노드들을 모두 차례로 방문한다.
   → queue에서 꺼낸 노드를 방문한다.
   → queue에서 꺼낸 노드와 인접한 노드들을 모두 방문한다.
   ⇒ 인접한 노드가 없다면, queue의 앞에서 노드를 꺼낸다.[dequeue]
   → queue에 방문한 노드를 삽입한다.[enqueue]
3. queue가 소진될 때까지 계속한다.

✔️ 너비 우선 탐색(BFS) 시간 복잡도 및 구현

• 인접 행렬로 구현 O(n^2)

vector<vector<int>> adjacent; // 주어진 인접행렬
vector<int> visited;  // 해당 node를 방문했는지 확인

void bfs(int node){
    queue<int> q;
    q.push(node);
    visited[node] = 1;

    while(!q.empty()){
        node = q.front();
        q.pop();

        for(int i=0; i<adjacent.size(); i++){

            if(!visited[i] && adjacent[node][i]){
                q.push(i);
                visited[i] = true;
            }
        }
    }
}

• 인접 리스트로 구현 O(n+e)

vector<vector<int>> adjacent; // 주어진 인접 리스트
vector<int> visited; // 해당 노드를 방문했는지 확인

void bfs(int node){
    queue<int> q;
    q.push(node);
    visited[node] = 1;

    while(!q.empty()){
        node = q.front();
        q.pop();

        for(int i=0; i<adjacent[node].size(); i++){
            int next = adjacent[node][i];
            if(!visited[next]){
                visited[next] = 1;
                q.push(next);
            }

        }
    }
}

References:
https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html
https://velog.io/@sukong/알고리즘-개념-너비우선탐색BFS-lp8zywtn
https://currygamedev.tistory.com/10