[알고리즘] - 너비 우선 탐색(BFS) #10

학습 목표

• BFS 알고리즘의 개념 및 동작 과정을 이해한다.   
• BFS 알고리즘을 구현한다.
• BFS 알고리즘의 시간 복잡도를 분석한다.

 

너비 우선 탐색(BFS, Breadth First Search)

1. 너비 우선 탐색이란?

 너비 우선 탐색은 깊이 우선 탐색처럼 그래프를 탐색하는 알고리즘입니다. 깊이 우선 탐색과는 다르게 시작 정점에서 가까운 정점부터 탐색해 나가는 방식입니다. 다시 말해, 출발 정점으로부터 탐색을 시작해 먼저 발견된 정점을 탐색한다고 생각하시면 됩니다. 어디서 비슷한 느낌의 자료구조를 보신 적이 있으실 겁니다! 바로 먼저 들어온(First In) 데이터를 먼저 처리(First Out)하는 Queue 입니다. 갑자기 이처럼 Queue를 언급하는 이유는 너비 우선 탐색에서 사용되기 때문입니다. 자세한 내용은 밑에서 설명해드리도록 하고 너비 우선 탐색의 간단한 활용처를 말씀드리겠습니다.

 

 너비 우선 탐색은 위에서 언급했듯이 출발 정점에서 가까운 정점을 우선적으로 탐색한다는 특징을 갖고 있습니다. 이는 다르게 해석하면 출발 정점으로 가까운 거리에 있는 정점을 탐색한다는 말이며, 어떤 조건에서의 최단 거리 혹은 최솟값을 찾는 데 활용됩니다. 나중에 다룰 최단거리 알고리즘인 다익스트라의 기본이 되기도 합니다. 개인적인 경험을 더해 말씀드리자면, 위에서 언급한 개념 및 특징을 기반으로 여러 기업의 코딩테스트에서 자주 출제되는 개념입니다. 그렇기 때문에 이전 포스팅과는 다르게 글 하단에 너비 우선 탐색을 활용해 해결할 수 있는 알고리즘 문제도 링크를 기재했으니 욕심이 있으신 분들은 한번 해결해보시길 추천드립니다. 이제부터 본격적으로 너비 우선 탐색에 대해서 설명해드리도록 하겠습니다.

 

2. 알고리즘 동작 과정

1. 출발 정점번호에 대한 방문 정보를 갱신하고, Queue 에 Push한다.
2. Queue 에서 하나의 정점(현재 정점)을 꺼낸다.
3. 현재 정점과 연결된 다른 정점의 방문 정보를 확인한다.
4. 연결된 정점이 이미 방문된 상태라면 무시하고, 그렇지 않다면 방문 정보를 갱신 후 Queue에 Push한다.
5. 2~4 과정을 Queue 에 정점이 들어있지 않을 때 까지 반복한다.

 

* 여기서 왜 방문표시를 먼저하고, Queue 에 push 하는지 궁금하신 분이 있으실 것 같습니다. 그 이유는 너비 우선 탐색은 먼저 방문한 정점을 먼저 탐색한다고 말씀드렸습니다. 그렇기 때문에 한 정점이 먼저 등장했다는 것은 나중에 발견돼도 이미 방문되어 있을 것이라는 의미입니다. 따라서 이미 발견된 정점을 큐에 push 하는 행위는 무의미한 행위입니다. 오히려 쓸모없는 연산이 발생하는 것입니다. 따라서 확인되는 순간  방문 표시를 하는 것입니다. 아직도 헷갈리신다면, "방문 표시"를 발견 여부를 체크했다고 해석하셔도 좋습니다.

 

 

3. 소스코드

- 인접 행렬

#include <iostream>
#include <queue>

using namespace std;

int g[5][5], start; 
bool visited[5];
queue<int> q;
void addEdge(int u, int v){
    g[u][v] = 1;
    g[v][u] = 1;
}
int main(){
    
    //간선 추가
    addEdge(0,1);
    addEdge(2,3);
    addEdge(3,4);
    addEdge(4,1);

    //시작 정점을 큐에 push
    cin >> start;
    visited[start] = true;
    q.push(start);

    while(!q.empty()){
        //정점 방문
        int now = q.front();
        q.pop();
        cout << now << " 방문\n" ;

        //인접 행렬로 구현하여 간선 유무를 직접 조사한다.
        for(int i = 0; i < 5; i++){
            //now 정점과 i 정점 사이의 간선이 존재하고 i 정점을 방문하지 않았을 때
            if(g[now][i] && !visited[i]){
                //방문 표시 후 큐에 입력
                visited[i] = true;
                q.push(i);
            }
        }
    }
    return 0;
}

- 인접 리스트

#include <iostream>
#include <queue>
#include <list>

using namespace std;

int start; 
bool visited[5];
queue<int> q;
list<int> g[5];
void addEdge(int u, int v){
    g[u].push_front(v);
    g[v].push_front(u);
}
int main(){
    
    //간선 추가
    addEdge(0,1);
    addEdge(2,3);
    addEdge(3,4);
    addEdge(4,1);

    //시작 정점을 큐에 push
    cin >> start;
    visited[start] = true;
    q.push(start);

    while(!q.empty()){
        //정점 방문
        int now = q.front();
        q.pop();
        cout << now << " 방문\n" ;

        //인접 행렬로 구현하여 간선 유무를 직접 조사한다.
        for(list<int>::iterator iter = g[now].begin(); iter != g[now].end() ; iter++){
            //iter이 가르키는 정점을 방문하지 않았을 때
            if(!visited[*iter]){
                //방문 표시 후 큐에 입력
                visited[*iter] = true;
                q.push(*iter);
            }
        }
    }
    return 0;
}

4. 시간복잡도

 BFS 의 시간복잡도는 그래프 표현 방법에 따라서 달라집니다. 인접 행렬로 그래프를 표현했다면 한 정점에서 다른 정점간의 간선 유무를 파악하기 위해서는 직접 조사를 해야 합니다. 이 과정에서 유효하지 않은 간선(g[u][v]==0)도 조사해야 하기 때문에 인접 행렬의 경우 행렬 크기인 O(V^2)의 시간 복잡도가 소요됩니다. 인접리스트는 인접 행렬과는 다르게 그래프에 유효한 간선만 리스트 형태로 가지고 있습니다. 그렇기 때문에 각 정점을 도는 데 O(V) 만큼의 시간 복잡도와 유효 간선을 파악하는 데 O(E) 만큼의 소요합니다. 따라서 인접리스트는 O(V+E) 만큼의 시간복잡도를 보입니다.

 

5. 정리

• 시작 정점에서 가까운 정점부터 탐색해 나가는 방식의 그래프 탐색 알고리즘이다.
• 알고리즘의 동작 구조상 Queue 를 사용한다.
• 특정 조건에서의 최단 거리 혹은 최솟값을 찾는 데 활용된다.
• 인접 행렬로 구현하면 O(V^2) 의 시간복잡도를 갖고, 인접리스트로 구현하면O(E+V)의 시간복잡도를 갖는다. 

6. 관련 문제

★☆☆ 단지 번호 붙이기 https://www.acmicpc.net/problem/2667

★★☆ 불 https://www.acmicpc.net/problem/5427 

★★★ 통나무 옮기기 https://www.acmicpc.net/problem/1938