[알고리즘] 너비 우선 탐색 (BFS, Breadth-First Search)

그래프 탐색 ?

하나의 정점(root)로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 탐색 방식이다.

너비 우선 탐색(BFS) ?

💡 루트 노드에서 시작하여 거리에 따라 단계별로 탐색하는 방법

• 어떤 노드를 방문했었는지에 대한 여부를 반드시 검사해야 한다.
  • 이를 검사하지 않을 경우 방문했던 곳을 또 방문하는 무한루프에 빠질 수 있다.
• 방문한 노드들을 차례로 저장한 후 꺼낼 수 있도록 큐(Queue)를 사용한다.
• 재귀적으로 동작하지 않는다.
• ‘Prim’, ‘Dijkstra’ 알고리즘과 유사하다.

💡 왜 굳이 큐(queue) 자료구조를 사용하는걸까?
탐색되는 점들을 저장하는 자료구조로 큐(queue)를 이용하는 이유는
먼저 탐색되는 위치를 먼저 빼내서 인접한 점들을 본다는 요구 사항 때문이다.
이러한 요구 사항은 FIFO(First In First Out) 라고 불리며,
이를 지원하는 가장 간단하고 빠르고 컴팩트한 자료구조가 큐(queue)이기 때문이다.

💡 ‘최단거리’ 문제에서 너비우선탐색(BFS) 사용하기
BFS가 빛을 발하는 경우는 그래프의 간선의 가중치가 모두 동일할 때 나타난다.
시작점에서 모든 점까지의 최단 거리는 달리 말하면 필요한 최소 간선(Edge) 개수로 표현할 수 있다.
BFS는 시작점에서 가까운 점들부터 탐색이 되기 때문에, 탐색하는 과정에서 사용되는 간선의 개수를 체크해 나아가면
그래프의 간선의 가중치가 모두 동일한 경우 최단 거리를 O(V+E)에 구할수 있다.

동작 과정

1. 시작점인 1을 큐에 넣고 방문처리를 한다.
2. 1을 꺼내고 인접한 정점인 2,3,8을 큐에 넣고 방문처리를 한다.
3. 큐에서 2를 꺼내고 방문하지 않은 7을 꺼내서 방문처리
4. 큐에서 3을 꺼내고 방문하지 않은 4,5를 꺼내서 방문처리
5. 위와 같이 큐에서 더이상 꺼낼것이 없을때까지 반복

코드 (C++)

// 코드 참고 : https://github.com/ndb796/python-for-coding-test

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

bool visited[9];
vector<int> graph[9];

// BFS 함수 정의
void bfs(int start) {
    queue<int> q;
    q.push(start); // 첫 노드를 queue에 삽입
    visited[start] = true; // 첫 노드를 방문 처리

    // 큐가 빌 때까지 반복
    while (!q.empty()) {
        // 큐에서 하나의 원소를 뽑아 출력
        int x = q.front();
        q.pop();
        cout << x << ' ';
        // 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for (int i = 0; i < graph[x].size(); i++) {
            int y = graph[x][i];
            if (!visited[y]) {
                q.push(y);
                visited[y] = true;
            }
        }
    }
}

int main(void) {
    // 노드 1에 연결된 노드 정보 저장 
    graph[1].push_back(2);
    graph[1].push_back(3);
    graph[1].push_back(8);

    // 노드 2에 연결된 노드 정보 저장 
    graph[2].push_back(1);
    graph[2].push_back(7);

    // 노드 3에 연결된 노드 정보 저장 
    graph[3].push_back(1);
    graph[3].push_back(4);
    graph[3].push_back(5);

    // 노드 4에 연결된 노드 정보 저장 
    graph[4].push_back(3);
    graph[4].push_back(5);

    // 노드 5에 연결된 노드 정보 저장 
    graph[5].push_back(3);
    graph[5].push_back(4);

    // 노드 6에 연결된 노드 정보 저장 
    graph[6].push_back(7);

    // 노드 7에 연결된 노드 정보 저장 
    graph[7].push_back(2);
    graph[7].push_back(6);
    graph[7].push_back(8);

    // 노드 8에 연결된 노드 정보 저장 
    graph[8].push_back(1);
    graph[8].push_back(7);

    bfs(1);
}

---

참고 링크

• https://jin1ib.tistory.com/entry/BFS-DFS-1
• https://hongku.tistory.com/156
• https://better-tomorrow.tistory.com/entry/DFS-BFS-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0