[알고리즘] BFS(깊이 우선 탐색)

📌 Intro

그래프 탐색의 기본은 BFS와 DFS다. 그 중 BFS에 대해 알아보도록 하자.

📌 BFS(너비 우선 탐색)

BFS란 Breadth-First Search로 너비 우선 탐색을 말하며 시작 노드로부터 인접한 노드를 먼저 탐색하고 멀리 떨어져있는 노드를 가장 나중에 방문하는 방법이다.
보통 BFS는 두 노드 사이의 최단 경로를 구할 때나 임의의 경로를 찾고 싶을 때 많이 사용한다.
BFS는 자료구조 큐(Qeueu)를 이용하여 구현할 수 있다.

인접 리스트로 표현된 그래프의 경우 시간 복잡도는 O(N+E)가 된다. 인접 행렬로 표현된 그래프의 경우 시간 복잡도는 O(N^2)이 된다. 간선의 숫자가 적다면 인접 행렬보다 인접 리스트를 사용하는 것이 시간상 유리하다.

STEP 0

다음과 같은 그래프에서 BFS로 탐색하는 방법에 대해 자세하게 알아보도록 하자. BFS를 활용하는 대부분의 문제에서 작은 번호를 먼저 처리하도록 요구하기 때문에 이 글에서도 작은 번호부터 처리할 것이다. 방문 처리된 노드는 회색으로, 큐에서 꺼내 현재 처리하는 노드는 하늘색으로 표시하겠다.

 

STEP 1

시작 노드로는 1번 노드로 지정한다. 따라서 1번 노드를 큐에 추가하고 방문 처리 한다.

 

STEP 2

큐의 가장 앞에 있는 원소인 1번 노드를 꺼낸 뒤 1번 노드와 연결되어 있고 방문하지 않은 노드 4번, 6번 노드를 큐에 추가하고 방문 처리한다.

 

STEP 3

큐의 가장 앞에 있는 원소인 4번 노드를 꺼낸 뒤 4번 노드와 연결되어 있고 방문하지 않은 노드인 3번 노드를 큐에 추가하고 방문 처리한다.

 

STEP 4

큐의 가장 앞에 있는 원소인 6번 노드를 꺼낸 뒤 6번 노드와 연결되어 있고 방문하지 않은 노드인 5번 노드를 큐에 추가하고 방문 처리한다. 이 때 1번 노드 역시 6번 노드와 연결되어 있지만 이미 방문 표시가 되어있기 때문에 큐에 추가하지 않는다.

 

STEP 5

큐의 가장 앞에 있는 원소인 3번 노드를 꺼낸 뒤 3번 노드와 연결된 노드 중 방문하지 않은 노드는 없기 때문에 종료한다.

 

STEP 6

큐에서 가장 앞에 있는 원소인 5번 노드를 꺼낸 뒤 5번 노드와 연결되어 있고 방문하지 않은 노드인 2번 노드를 큐에 추가하고 방문 처리한다.

 

STEP 7

큐에서 가장 앞에 있는 원소인 6번 노드를 꺼낸 뒤 5번 노드와 연결되어 있고 방문하지 않은 노드는 없기 때문에 종료되고 큐에 남은 원소가 없기 때문에 전체 BFS역시 종료된다.

📌 BFS 구현

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

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

void BFS(int start){
    queue<int> q;
    visited[start] = true;
    q.push(start);

    while(!q.empty()){
        int cur = q.front();    // 현재 노드
        q.pop();

        // 현재 노드에서 방문이 가능한 노드 확인
        for(int i=0; i<graph[cur].size(); i++){
            int next = graph[cur][i];

            if(visited[next] == false){
                q.push(next);
                visited[next] = true;
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    graph[1].push_back(4);
    graph[4].push_back(1);

    graph[1].push_back(6);
    graph[6].push_back(1);

    graph[2].push_back(5);
    graph[5].push_back(2);

    graph[3].push_back(4);
    graph[4].push_back(3);

    graph[5].push_back(6);
    graph[6].push_back(5);

    BFS(1);

    return 0;
}

📌 관련 문제

1260번: DFS와 BFS

2606번: 바이러스

📌 참고

[1] https://blog.naver.com/ndb796/221230944971