graph

[알고리즘 / C++] BFS 알고리즘 (너비 우선 탐색)

BFS 알고리즘 C++

Table of Contents

Toggle

BFS 알고리즘 이란?

DFS 설명 보려면 이전 글을 참고하자

BFS(Breadth-First Search) 는 DFS와 더불어 그래프에서 많이 사용하는 알고리즘이다.

체감상 DFS보다 BFS를 사용하는 문제를 더 많이 접하게 되는 것 같다.

DFS와 마찬가지로 BFS 알고리즘은 한 노드에서 출발해 연결된 모든 노드들을 방문하게 된다.

하지만 DFS가 가능한 한 깊게 탐색하고 되돌아 오는 것에 반해 BFS는 가까운 모든 노드들을 먼저 방문한 후 깊이 들어가게 된다.

BFS 알고리즘 작동 방식

BFS 알고리즘이 어떻게 작동하는지 살펴보자

BFS는 큐(Queue) 자료구조를 사용해서 구현한다

큐 초기화
시작 노드 방문
인접 노드 큐에 추가
큐가 빌때까지 반복

DFS를 설명했던 노드 그림을 그대로 가져와서 설명해 보도록 하겠다.

큐 초기화

시작 노드는 0으로 설정하였다.

Queue : [0]

Queue : [1, 2]

2. 시작 노드 방문

3. 인접노드 큐에 추가

큐에서 시작노드 0을 뺀 후 0과 연결되어 있는 모든 노드들을 큐에 추가한다.

여기서는 1, 2가 연결되어 있기 때문에 queue에는 0, 1이 들어가게 된다.

4. 큐에 없어질때까지 반복

노드 1 방문

Queue : [2, 3]

큐는 FIFO로 먼저들어간 1이 먼저 나오게 된다.

1을 방문한 후 1과 연결된 노드들을 모두 추가해 준다.

여기서는 3이 있기 때문에 큐에 3을 넣어 준다.

노드 2 방문

Queue : [3, 4, 5]

큐의 제일 앞에 있는 2를 빼서 방문한다.

2와 연결되어 있는 노드들을 모두 큐에 넣는다.

여기서는 4, 5가 연결되어 있기 때문에 큐는 원래 있던 3과 4, 5가 추가된다.

노드 3 방문

Queue : [4, 5]

큐의 제일 앞에 있는 3을 꺼내어 방문한다.

3에는 더이상 연결되어 있는 노드가 없기 때문에 아무것도 추가하지 않는다.

노드 4 방문

Queue : [5]

큐의 제일 앞에 있는 4를 꺼내어 방문한다.

4도 더이상 연결되어 있는 노드가 없기 때문에 추가하지 않는다.

노드 5 방문

Queue : []

큐의 제일 앞에 있는 5를 꺼내어 방문한다.

더이상 추가할 노드가 없고, 큐도 비었기 때문에 BFS를 종료하게 된다.

결론

BFS 알고리즘 ( 너비 우선 탐색)은 주변 노드들을 먼저 탐색하기 때문에

0 -> 1 -> 2 -> 3 -> 4 -> 5의 순서대로 탐색하게 된다.

어떤 문제에서 BFS를 써야하는가

BFS는 활용도가 무궁무진하다고 생각한다.

그리고 그 중에 많이 쓰이는 것들을 몇개 추려 보았다

최단 경로 찾기 (노드 간, 2차원)
바이러스 문제
미로찾기

대부분의 문제 유형이 비슷한 느낌인데

그래프 문제에서 주로 최단경로, 적절한 길을 찾는 문제에 많이 사용한다고 생각하면 될 것 같다.

최단 경로에서 BFS가 유용한 이유는 BFS 알고리즘이 현재 노드의 인접 노드들을 하나씩 모두 확인하기 때문에 가장 먼저 찾아지는 경로가 곧 최단거리이기 때문이다!!

BFS 알고리즘 장단점 / 시간복잡도

장점

최단경로를 보장한다
알고리즘이 꽤 간단하다

단점

메모리 소모가 크다

비효율적이다.

최단경로를 찾을 수는 있지만 그래프의 크기가 매우 클 경우 메모리 소모가 크고 최악의 비효율적일 수 있다. 따라서 그래프의 크기가 크다면 dfs를 사용하는 것이 더 맞다.

시간복잡도

노드 수 (V), 간선 수 (E) 일때

O(V+E)의 시간복잡도를 가진다.

C++ BFS 알고리즘 구현

BFS 알고리즘을 #include <queue> 헤더를 사용해서 구현하면 간단하게 할 수 있다.

DFS와 마찬가지로 visited 배열이 있어야 하고

각 노드에 방문할 때마다 visited 배열을 true로 만들고 연결된 노드들을 큐에 넣어 준다.

그리고 큐가 빌때까지(모두 방문할때까지) while문을 돌리며 반복한다.

void BFS(int V, vector<int> adj[], int s) {
    vector<bool> visited(V, false);
    queue<int> queue;

    visited[s] = true;
    queue.push(s);

    while(!queue.empty()) {
        s = queue.front();
        cout << s << " ";
        queue.pop();

        for (int i = 0; i < adj[s].size(); i++) {
            if (!visited[adj[s][i]]) {
                visited[adj[s][i]] = true;
                queue.push(adj[s][i]);
            }
        }
    }
}

전체적인 방법은 DFS와 비슷한 것 같다.

단지 queue냐 stack이냐의 차이로 구현하면 될 것 같다.

heaven