110. Breadth First Search

너비 우선 탐색(Breadth First Search, BFS)^[각주:1]은 노드를 탐색하고, 그 노드와 인접한 노드를 탐색하고, 그 노드들과 인접한 노드를 탐색하는 식으로 탐색을 시작한 노드에서 가까운 노드부터 차례로 탐색을 진행하는 탐색 방법이다. 이전에 탐색한 노드들과 인접해서 이후에 탐색할 예정이지만 아직 탐색하지 않은 노드들을 저장하기 위해 보통 큐가 사용된다. 탐색 과정에서 시작 노드에서 각각의 노드까지의 최단 경로의 길이를 알 수 있게 된다. DFS와 마찬가지로 인접한 노드가 여러 개 있을 경우 문제 상황에 맞게 탐색 순서를 정하면 된다.

 

DFS를 설명한 글에 나온 그래프의 노드 $\text{D}$에서 BFS를 시작하면 BFS는 다음과 같이 진행된다.

먼저 노드 $\text{D}$를 방문한다. 노드 $\text{D}$는 노드 $\text{E}$, $\text{F}$, $\text{I}$와 인접해 있다. 큐에 노드 $\text{F}$, $\text{I}$, $\text{E}$의 순서로 들어갔다고 가정한다.

이제 큐의 맨 앞 원소를 꺼내서 그 노드와 인접한 노드들 중 아직 큐에 들어가지 않은 노드들을 큐에 넣는 과정을 반복한다. 큐에서 노드 $\text{F}$를 꺼내고, 인접한 노드인 $\text{A}$와 $\text{B}$를 큐에 넣는다.

노드 $\text{I}$를 방문하고 인접한 노드인 $\text{G}$, $\text{C}$, $\text{H}$를 큐에 넣는다.

나머지 노드들을 차례로 방문한다. 모든 노드가 큐에 한 번씩 들어갔으므로 이때부터는 큐에 노드가 추가로 들어가지는 않는다.

노드의 방문 순서는 다음과 같다.

$\text{D F I E A B G C H}$

 

BFS의 실행이 종료되었을 때 각각의 노드는 시작 노드로부터의 최단 거리에 대한 정보를 알 수 있다. 위 그림에서 빨간색은 거리가 $0$인 노드들, 파란색은 거리가 $1$인 노드들, 초록색은 거리가 $2$인 노드들이다.

 

구현은 다음과 같다. DFS와 마찬가지로 각각의 정점이 큐에 한 번씩 들어갔다 나오고 각각의 간선을 두 번씩 확인하므로 시간복잡도는 $\Theta(n+m)$이다.

#import<bits/stdc++.h>
using namespace std;
int d[100005]; // d는 distance의 약자로 사용됨
vector<int>v, e[100005];
queue<int>Q;
void bfs()
{
    int node;
    for(; Q.size(); Q.pop())
    {
        node = Q.front();
        v.push_back(node);
        for(auto &p: e[node])
        {
            if(d[p] == -1)
            {
                d[p] = d[node] + 1;
                Q.push(p);
            }
        }
    }
}
int main()
{
    int m, n, x, y;
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    fill(d + 1, d + n + 1, -1);
    d[1] = 0;
    Q.push(1); // BFS 시작 정점
    bfs();
}

이렇게 구현할 경우 bfs 함수를 따로 분리하지 않고 main 함수 내에서 BFS를 직접 실행하는 방법도 있다.

#import<bits/stdc++.h>
using namespace std;
int d[100005];
vector<int>v, e[100005];
queue<int>Q;
int main()
{
    int m, n, node, x, y;
    cin >> n >> m;
    for(int i = 0; i < m; i++)
    {
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    fill(d + 1, d + n + 1, -1);
    d[1] = 0;
    for(Q.push(1); Q.size(); Q.pop())
    {
        node = Q.front();
        v.push_back(node);
        for(auto &p: e[node])
        {
            if(d[p] == -1)
            {
                d[p] = d[node] + 1;
                Q.push(p);
            }
        }
    }
}

dfs 함수에서 방문 여부를 체크했던 $\text{vi}$ 배열의 이름이 $d$로 바뀌었다. BFS의 실행이 끝나면 $d[i]$의 값은 시작 정점에서 $i$번 정점까지의 최단 거리가 된다.

 

[연습문제]

 

BOJ 1260. DFS와 BFS (Silver II)

정점 $V$를 시작 정점으로 해서 DFS, BFS를 실행한다. 인접한 정점이 여러 개일 경우 번호가 작은 쪽을 먼저 방문하라는 조건이 있으므로 간선을 벡터에 넣은 후 각각의 벡터를 정렬해야 한다.

 

BOJ 2644. 촌수계산 (Silver II)

트리에서 BFS를 실행한다.

 

BOJ 1697. 숨바꼭질 (Silver I)

어떤 것을 간선으로 할지 정해야 하는데, 각각의 점을 정점으로 간주하면 정점 $x$와 $x+1$을 잇는 양방향 간선과 정점 $x$에서 $2x$로 가는 단방향 간선이 존재한다고 할 수 있다. 이 상태로 BFS를 실행하면 되는데 실행 중 번호가 너무 큰 정점을 탐색하지 않도록 주의해야 한다.

 

BOJ 12851. 숨바꼭질 2 (Gold V)

여기서는 최단 경로의 개수도 구해야 하는데, 이것은 각각의 정점에 대해 시작 정점에서 그 정점으로 가는 최단 경로의 개수를 체크해 놓으면 구할 수 있다.

 

BOJ 13913. 숨바꼭질 4 (Gold IV)

이 문제는 최단 경로를 직접 구해야 한다. 각각의 정점이 큐에 들어갈 때 어떤 정점을 탐색했는지를 체크하면 이것이 최단 경로에서 그 정점의 이전 정점과 같으므로 도착 정점에서 역추적을 하면 최단 경로를 구할 수 있다.

 

BOJ 2585. 경비행기 (Gold II)

비행장을 정점으로 두면, 비행장 사이의 거리가 연료통이 감당할 수 있는 거리인 경우 정점 사이에 간선이 존재한다고 할 수 있다. 연료통 크기에 따른 최소 급유 횟수는 증가하지 않으므로 연료통 크기로 매개변수 탐색을 하면 된다.

 

BOJ 8111. 0과 1 (Platinum V)

이번에는 나머지를 기준으로 그래프 모델링을 해야 하는데, 정점의 번호가 $0$부터 $N-1$까지 존재하고 정점 $x$에서 정점 $10x\,\bmod\,N$과 $(10x+1)\,\bmod\,N$으로 가는 단방향 간선이 있다고 생각할 수 있다. 이 그래프에서 BFS를 실행하고 역추적을 하면 되는데, $0$과 $0$보다 큰 $N$의 배수를 구별해 주어야 한다.

 

BOJ 8111. 0과 1 - 2 (Platinum IV)

8111번 문제에서 $N$의 제한이 커졌다. 8111번은 문자열로 표현된 수 자체를 큐에 넣는 등 역추적을 안 할 수 있는데 이 문제는 역추적을 해야 한다.

 

BOJ 15019. Distinctive Character (Platinum IV)

이번에는 비트를 이용한 BFS 문제이다. 두 정점 번호의 비트가 한 개만 다를 때 정점 사이에 간선이 존재한다고 하고 입력에 주어진 이진수를 모두 큐에 넣고 BFS를 실행한 다음 가장 마지막에 큐에서 나오는 이진수를 출력하면 맞는다.

 

→ solved.ac tag: bfs

---

1. '넓이 우선 탐색'이라는 표현도 가끔씩 등장하는데 깊이, 너비가 $1$차원 측도인 반면 넓이는 $2$차원 측도이므로 적절한 표현이 아니다. [본문으로]