너비 우선 탐색¶

너비 우선 탐색은 그래프에서 사용하는 기본적이고 필수적인 탐색 알고리즘 중 하나입니다.

알고리즘의 동작 방식에 따라, 너비 우선 탐색으로 찾은 임의의 노드까지의 경로는 그 노드까지의 최단 경로, 즉 가중치 없는 그래프에서 간선의 수가 가장 적은 경로가 됩니다.

이 알고리즘은 $O(n + m)$ 시간에 동작하며, 여기서 $n$은 정점의 수이고 $m$은 간선의 수입니다.

알고리즘 설명¶

이 알고리즘은 가중치 없는 그래프와 시작 정점 $s$의 번호를 입력으로 받습니다. 입력 그래프는 방향 그래프일 수도 있고 무방향 그래프일 수도 있으며, 알고리즘에는 차이가 없습니다.

이 알고리즘은 그래프 위로 불이 번져 나가는 과정으로 이해할 수 있습니다. 0번째 단계에서는 시작 정점 $s$에만 불이 붙어 있습니다. 각 단계마다 각 정점에서 타오르는 불이 그 정점의 모든 이웃으로 번집니다. 알고리즘이 한 번 반복될 때마다 "불의 고리"가 너비 방향으로 한 단위씩 넓어집니다(알고리즘의 이름이 여기서 유래했습니다).

더 정확히 말하면, 알고리즘은 다음과 같이 기술할 수 있습니다. 처리할 정점을 담을 큐 $q$와, 각 정점에 불이 붙었는지(즉, 방문했는지) 여부를 나타내는 불리언 배열 $used[]$를 만듭니다.

처음에는 시작 정점 $s$를 큐에 넣고 $used[s] = true$로 설정하며, 나머지 모든 정점 $v$에 대해서는 $used[v] = false$로 설정합니다. 그런 다음 큐가 빌 때까지 루프를 돌며, 각 반복마다 큐의 앞에서 정점 하나를 꺼냅니다. 이 정점에서 나가는 모든 간선을 순회하면서, 그중 아직 불이 붙지 않은 정점으로 향하는 간선이 있으면 그 정점에 불을 붙이고 큐에 넣습니다.

그 결과, 큐가 비었을 때 "불의 고리"는 시작 정점 $s$에서 도달할 수 있는 모든 정점을 포함하며, 각 정점에는 가능한 가장 짧은 방법으로 도달하게 됩니다. 또한 최단 경로의 길이를 계산할 수 있고(경로 길이 배열 $d[]$만 유지하면 됩니다), 이 모든 최단 경로를 복원하기 위한 정보도 저장할 수 있습니다(이를 위해서는 각 정점마다 그 정점에 도달하기 직전의 정점을 저장하는 "부모" 배열 $p[]$를 유지해야 합니다).

구현¶

앞에서 설명한 알고리즘의 코드를 C++와 Java로 작성합니다.

C++Java

vector<vector<int>> adj;  // adjacency list representation
int n; // number of nodes
int s; // source vertex

queue<int> q;
vector<bool> used(n);
vector<int> d(n), p(n);

q.push(s);
used[s] = true;
p[s] = -1;
while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (int u : adj[v]) {
        if (!used[u]) {
            used[u] = true;
            q.push(u);
            d[u] = d[v] + 1;
            p[u] = v;
        }
    }
}

ArrayList<ArrayList<Integer>> adj = new ArrayList<>(); // adjacency list representation

int n; // number of nodes
int s; // source vertex


LinkedList<Integer> q = new LinkedList<Integer>();
boolean used[] = new boolean[n];
int d[] = new int[n];
int p[] = new int[n];

q.push(s);
used[s] = true;
p[s] = -1;
while (!q.isEmpty()) {
    int v = q.pop();
    for (int u : adj.get(v)) {
        if (!used[u]) {
            used[u] = true;
            q.push(u);
            d[u] = d[v] + 1;
            p[u] = v;
        }
    }
}

시작 정점에서 어떤 정점 $u$까지의 최단 경로를 복원하여 출력해야 한다면, 다음과 같이 할 수 있습니다.

C++Java

if (!used[u]) {
    cout << "No path!";
} else {
    vector<int> path;
    for (int v = u; v != -1; v = p[v])
        path.push_back(v);
    reverse(path.begin(), path.end());
    cout << "Path: ";
    for (int v : path)
        cout << v << " ";
}

if (!used[u]) {
    System.out.println("No path!");
} else {
    ArrayList<Integer> path = new ArrayList<Integer>();
    for (int v = u; v != -1; v = p[v])
        path.add(v);
    Collections.reverse(path);
    for(int v : path)
        System.out.println(v);
}

BFS의 활용¶

가중치 없는 그래프에서 시작 정점으로부터 다른 정점들까지의 최단 경로를 찾습니다.
무방향 그래프의 모든 연결 요소를 $O(n + m)$ 시간에 찾습니다. 이를 위해서는 이전 실행에서 이미 방문한 정점을 제외한 각 정점에서 BFS를 실행하기만 하면 됩니다. 즉, 각 정점에서 일반적인 BFS를 수행하되 새로운 연결 요소를 찾을 때마다 배열 $used[]$를 초기화하지 않으며, 전체 실행 시간은 여전히 $O(n + m)$입니다(배열 $used []$를 초기화하지 않고 그래프에서 BFS를 여러 번 수행하는 것을 연속 너비 우선 탐색이라고 부릅니다).
게임의 각 상태를 그래프의 정점으로, 한 상태에서 다른 상태로의 전이를 그래프의 간선으로 나타낼 수 있다면, 가장 적은 이동 횟수로 문제나 게임의 해를 찾습니다.
가중치가 0 또는 1인 그래프에서 최단 경로를 찾습니다. 이는 일반적인 너비 우선 탐색을 약간만 수정하면 됩니다. 배열 $used[]$를 유지하는 대신, 정점까지의 거리가 현재 찾은 거리보다 짧은지 확인하고, 현재 간선의 가중치가 0이면 큐의 맨 앞에, 그렇지 않으면 큐의 맨 뒤에 정점을 추가합니다. 이 수정 방법은 0-1 BFS 문서에서 더 자세히 설명합니다.
가중치 없는 그래프(방향 그래프)에서 최단 사이클 찾기: 각 정점에서 너비 우선 탐색을 시작합니다. 현재 정점에서 시작 정점으로 되돌아가려는 순간, 시작 정점을 포함하는 최단 사이클을 찾은 것입니다. 이 시점에서 BFS를 멈추고 다음 정점에서 새로운 BFS를 시작할 수 있습니다. 이렇게 찾은 모든 사이클(각 BFS마다 최대 하나) 중에서 가장 짧은 것을 선택합니다.
주어진 정점 쌍 $(a, b)$ 사이의 최단 경로 중 하나 위에 놓인 모든 간선을 찾습니다. 이를 위해 너비 우선 탐색을 두 번 실행합니다. 한 번은 $a$에서, 한 번은 $b$에서 실행합니다. $d_a []$를 첫 번째 BFS($a$에서 시작)로 얻은 최단 거리를 담은 배열이라 하고, $d_b []$를 $b$에서 시작한 두 번째 BFS로 얻은 최단 거리를 담은 배열이라 합시다. 이제 $d_a [u] < d_a [v]$, 즉 $a$에서 $b$로 갈 때 $u$가 $v$보다 먼저 나온다고 가정하면, 모든 간선 $(u, v)$에 대해 그 간선이 $a$와 $b$ 사이의 최단 경로 중 하나 위에 놓이는지 쉽게 확인할 수 있습니다. 판별 기준은 $d_a [u] + 1 + d_b [v] = d_a [b]$라는 조건입니다.
주어진 정점 쌍 $(a, b)$ 사이의 최단 경로 중 하나 위에 놓인 모든 정점을 찾습니다. 이를 위해 너비 우선 탐색을 두 번 실행합니다. 한 번은 $a$에서, 한 번은 $b$에서 실행합니다. $d_a []$를 첫 번째 BFS($a$에서 시작)로 얻은 최단 거리를 담은 배열이라 하고, $d_b []$를 두 번째 BFS($b$에서 시작)로 얻은 최단 거리를 담은 배열이라 합시다. 이제 각 정점에 대해 그 정점이 $a$와 $b$ 사이의 최단 경로 중 하나 위에 놓이는지 쉽게 확인할 수 있습니다. 판별 기준은 $d_a [v] + d_b [v] = d_a [b]$라는 조건입니다.
가중치 없는 그래프에서 시작 정점 $s$로부터 목표 정점 $t$까지 길이가 짝수인 최단 워크 찾기: 이를 위해 정점이 상태 $(v, c)$인 보조 그래프를 구성해야 합니다. 여기서 $v$는 현재 노드이고, $c = 0$ 또는 $c = 1$은 현재 홀짝성입니다. 원래 그래프의 모든 간선 $(u, v)$는 이 새 그래프에서 두 간선 $((u, 0), (v, 1))$과 $((u, 1), (v, 0))$으로 바뀝니다. 그다음 BFS를 실행하여 시작 정점 $(s, 0)$에서 끝 정점 $(t, 0)$까지의 최단 워크를 찾습니다.
참고: 이 항목에서 "경로" 대신 "워크"라는 용어를 쓰는 데에는 이유가 있습니다. 찾은 워크의 길이를 짝수로 만들기 위해 정점이 반복될 수 있기 때문입니다. 길이가 짝수인 최단 경로를 찾는 문제는 방향 그래프에서는 NP-완전이며, 무방향 그래프에서는 선형 시간에 풀 수 있지만 훨씬 더 복잡한 접근 방식이 필요합니다.

너비 우선 탐색¶

알고리즘 설명¶

구현¶

BFS의 활용¶

연습 문제¶