[자료구조] 14-2. 넓이 우선 탐색 알고리즘의 응용 (1)

bfs로 그래프의 거리를 측정하는 문제를 살펴보자. 맨 처음 살펴볼 문제는 '단일 출발점 최단 거리 찾기'이다. 하나의 출발점에서 시작해 다른 모든 버텍스로 가는 최단 거리를 찾는 문제다.

만약 버텍스 v0에서 버텍스 u까지 가는 경로를 v0, v1, v2...vk, u라고 한다면, 패스는 (v0, v1), (v1, v2)...(vk-1, vk), (vk. u)와 같은 엣지들의 집합이다. 이 경로의 cost는 엣지에 있는 가중치의 합으로 생각할 수 있다.

이러한 가중치 그래프가 있다고 할 때, A와 B 버텍스 사이에 가중치가 2라면, 그 사이에 버텍스를 하나 추가한다. B와 E 사이의 가중치는 3이므로 2개를 추가할 수 있다. 가중치가 w인 엣지에 대해 w-1개의 버텍스를 추가하면 동일한 거리를 가지며, 가중치가 없는 그래프가 된다.

이 그래프에서 bfs를 수행하면 최단 거리를 측정할 수 있는데, 대신 매우 비효율적이다. 시간복잡도가 O(n+m)이면 m은 가중치에 비례한다. 그래서 가중치가 높은 그래프는 같은 모양의 그래프여도 성능의 차이가 매우 커진다.

만약 이렇게 가중치가 100, 200이라면 99개와 199개의 버텍스를 추가해야 하므로 매우 비효율적이다.

가까운 버텍스는 더 먼저 바운한다는 bfs의 기본 개념을 가지고 발전시킨 다른 아이디어를 살펴보자.

알람시계 알고리즘은 최단 거리 탐색 알고리즘에서 가장 유명한 dijkstra's 알고리즘에 기반한다. S에서 A까지의 최단 거리와, B까지의 최단 거리를 구해보자.

S에서 출발할 때의 시간은 0이다. A까지는 100, B까지는 200이 걸린다. 여기에 알람시계를 맞출 것이다. 100초 뒤에는 A에서, 200초 뒤에는 B에서 일어날 것이라고 알람을 맞춘다.

그래서 t가 100일 때 A에 도착하고, B까지의 거리를 보니 50이다. 그럼 나는 50만큼만 더 기다리면 된다. A까지 100, B까지 50이 총 시간인 것이다. 이 두 거리를 고려해서 B에 대한 알람 시간을 갱신한다. 이것이 최단 거리를 측정하는 알람시계 알고리즘이다.

시작점이 s일때 그 시간을 0으로 해놓고 모든 버텍스에 도착할 때까지(더 이상 알람이 없을 때까지) 반복한다.

알람이 울리면 즉, 어떤 버텍스 u에 도착한 t에서 알람이 울렸다고 생각해보자. u까지의 거리는 t가 된다. 그리고 u에서 v까지는 l(u, v)만큼 걸린다.

s -- T --> u -- l(u, v) --> v 

원래 s-->v에 걸린 알람이 v's라고 하자. v's > T + l(u,v) 라면, v's의 값을 T + l(u,v)로 갱신한다.

제일 핵심이 되는 부분이 바로 위의 빨간 네모 부분이다. 기존에 설정한 거리와 새로 계산한 거리를 비교해 갱신하는 과정을 edge relaxation 또는 principle of relaxation이라고 한다. 더 정확한 값으로 갱신해서 예측의 정확도를 높이는 과정이라고 말할 수 있다.

이 edge relaxation이 dikstra's 알고리즘의 핵심적인 아이디어다. 수 많은 알고리즘 중에서 가장 중요한 것 중 하나라고 말할 수 있다.

1. 하나의 출발점에서 모든 버텍스로 가는 최단 거리를 구하는 알고리즘이다.

2. 방향/무방향 그래프에 상관없이 적용된다.

3. 가중치에 음수가 있으면 작동하지 않는다.

구조는 간단하다.

1. 아직 모든 버텍스까지의 거리는 모르기 때문에 dist[u]를 무한대로 놓는다.

2. 어떤 버텍로부터 왔는지도 설정이 없으므로 null로, 시작하는 버텍스의 거리는 dist[s]=0으로 둔다.

3. 버텍슬르 넣어하 하나의 우선순위 큐를 만든다.

4. 우선순위 큐가 empty가 될때까지 while을 반복한다.

5. while 안에서는 우선 순위 큐에서 가장 거리가 짧은(알람이 가장 먼저 울리는) 버텍스를 min을 찾는다.

6. 그 버텍스에 연결된 다른 모든 버텍스들에 대해 원래 v까지 가는 거리 / u를 통해 v까지 가는 거리를 비교한다.

7. 후자가 더 작다면 값을 바꿔준다.

8. 갱신된 내용을 우선 순위 큐에 반영한다.

A에서 시작해 B, C, D, E까지 가는 최단 경로를 구해보자. 먼저, A에 대한 거리를 0으로 설정한다. 이것이 우선 순위 큐가 된다.(이전 자료 코드 상에서의 H)

처음에는 모든 버텍스들의 길이가 무한대로 설정되어 있지만, 그래프에서 보면 B까지의 거리가 4이므로 B에 4를, C까지의 거리가 2이므로 2를 넣어 우선순위 큐를 갱신한다.

이 상태에서 가장 짧은 것은 C이므로 C를 방문한다.

C에서 갈 수 있는 버텍스는 B, D, E다. A-C는 2, C-B는 1이므로 B의 가중치는 3이된다. A가 B로 직접 가는 4보다 작으므로 B값을 4에서 3으로 바꿔준다.

A-C-D는 6이고 무한대보다 작으므로 6으로 갱신된다. A-C-E는 7이고 무한대보다 작으므로 7로 갱신된다.

이제 우선 순위 큐 H를 보면, 방문했던 A와 C는 지워진다. 나머지 B, D, E 중에 제일 작은 B로 이동한다.

A-B 다음에 갈 수 있는 버텍스를 생각해보면, D와 E가 있다. A-D는 기존에 6이었고, A-E는 7이었다. A-B-D는 3+2 = 5이므로 D는 5로 갱신된다.

A-B-E는 큐를 보면 A-B가 3, 그래프상에서 B-E가 3이므로 6이다. 원래 E가 7이었으므로 6으로 갱신된다. 

지금 우선 순위 큐는 A, C에 이어 B가 지워졌다. D, E중 저 작은 버텍스인 D를 방문해야 한다.

D는 방문할 곳이 없다. 그냥 큐에서 지우고 E를 방문한다. E는 마지막 버텍스이므로 방문할 곳이 없다.

최종적으로 이와 같은 순서를 얻을 수 있다.

지금까지의 과정을 보면,

1. 각 버텍스에 대한 미니멈 코스트인 dist(u)를 저장한다.

2. 내가 누구로부터 왔는지 prev에 저장한다. prev(D)는 B, prev(B)는 C가 된다.

3. 그 경로의 값을 다 더하고 저장하면 최단 거리가 된다.

이 알고리즘의 시간 복잡도 분석은 조금 어렵다.

1. 모든 버텍스에 대해 수행하므로 O(n)

2. 우선 순위 큐를 초기화하는 과정을 A라고 한다.

3. 최솟값을 가져오는 연산을 B라고 한다. 이 연산은 n번 수행한다.

4. 버텍스 u에 연결된 모든 버텍스에 대해 for loop를 돌리는데, 사실 이것은 모든 버텍스가 아니라 엣지에 대해서 수행이 되므로 m*O(?)이다. 이것을 C락 부르자.

최종 시간 복잡도는 A+B+C다.

우선 순위 큐에는 배열 기반과 트리 기반 두 종류가 있다. 초기 dijkstra's 알고리즘은 트리 기반이 아니라 배열 기반의 우선 순위 큐를 사용했다. 

따라서,

1. A는 n개의 원소를 큐에 삽입하므로 O(n)이 걸린다.

2. 큐에서 최솟값을 제거해야하는데 배열 기반이므로 제거하는 데에 O(n) 걸리고 최종적으로 O(n^2)가 걸린다.

3. 큐를 갱신할 때에도 배열 기반의 큐에 포인터를 사용한다면 O(1)이지만, O(m) 번 반복해야 하므로 O(m)이다.

결국 최종 시간 복잡도는 O(n), O(n^2), O(m)의 합이므로 O(n^2)이라고 할 수 있다.

하지만 그 이후에, 피보나치 힙을 만들어 dijkstra's 알고리즘의 성능을 개선했다.

- 최솟값 검색: O(1)

- 최솟값 제거: O(log n)

- 추가, 히피파이, 머지: O(1)

다시 아까의 내용으로 돌아가보자.

B는 최솟값을 제거하는 연산이다. 여기에 피보나치 힙을 이용할 경우 O(log n)이 걸린다. 세 개를 다 더해보면 어떤 것이 더 큰지는 알 수 없으므로 O(m) + O(n log n)이 나온다.

정리하자면,

- 밀집 그래프: 엣지의 수는 O(n^2)

엣지가 n^2이므로 배열과 우선 순위 큐 모두 O(n^2)이 나온다.

- 희소 그래프: 엣지의 수는 m=O(n)

배열을 사용하면 O(n^2)이 나오지만, 피보나치 힙처럼 우선 순위 큐를 이용했을 경우는 O(n log n)이 나온다.