최단거리 문제 알고리즘에 대한 궁금증 정리
DFS, BFS와 다익스트라 알고리즘에 대한 여러가지 의문점
최단 경로 문제는 가중치가 없는 그래프에서는 보통 두 정점을 잇는 가장 적은 간선의 개수를 뜻하고, 가중치가 존재하는 그래프에서는 두 정점을 잇는 간선들의 가중치의 합 중 최소 가중치 합을 의미한다.
알고리즘을 공부하다보면, 가중치가 없는 그래프(unweighted graph)인 경우 BFS를 사용하고, 가중치가 0이거나 1일 때 역시 BFS를 사용한다고 배운다. 가중치가 여러 개가 존재한다면 다익스트라 알고리즘을 사용하라고 가르친다. 최단 거리 문제에서 DFS를 사용하지 않는 이유는 가능한 모든 경로를 탐색하는 DFS의 특징 상 BFS에 비해 효율적이지 않기 때문이다. 이번 글에는 왜 그러한 지에 대해 탐구하는 시간을 갖도록 하겠다.
Point 1. 최단 경로를 탐색할 때 DFS를 사용하지 않는 이유
- 방향성이 없는 undirected graph를 가정해보자.
- 안 될 이유는 없지만, 비효율적이기 때문이다.
- 일단 최단경로를 검색할 때 recursive하게 DFS를 구현하면 내가 원하는 vertex 간의 거리를 구할 수는 있다. 하지만 트리 형태라는 확증이 있어야 한다.
- 만약 그래프의 경우라면 내가 최종적으로 방문한 경로가 최단 경로인지 확신할 수 없기 때문이다. 이와 반대로, 트리의 경우라면 정점 간의 경로가 단 하나만 존재하기 때문에, 내가 방문한 경로는 무조건 최단 경로일 수밖에 없다. 아래의 코드를 보자.
//recursiveDFS.js
const shortestPathDfs = (startNode, stopNode) => {
const previous = new Map();
let shortestDistance = -1;
const dfs = (currentNode, depth) => {
if (currentNode === stopNode) {
shortestDistance = depth;
} else {
for (let neighbour of adjacencyList.get(currentNode)) {
previous.set(neighbour, currentNode);
dfs(neighbour, depth + 1);
}
}
};
dfs(startNode, 0);
return { shortestDistance, previous };
};- 위의 코드를 보면 currentNode와 stopNode가 일치할 때 shortestDistance를 현재 탐색 depth로 설정한다. 다시 말해서 내가 찾고자 하는 도착점을 찾았을 때, 시작점에서의 depth 값을 shortestDistance로 할당해주는 것이다.
- 만약 트리 형태가 아니라 그래프 형태가 문제에서 주어졌다면, 최종적으로 방문한 경로가 가장 최단 거리인 지 확신할 수 없다. 예를 들어 Node 4로 갈 수 있는 이전 정점이 Node 1, Node 2가 있다고 하자. 그렇다면 Node 1로 갈 때의 정답과 Node 2로 갈 때의 정답이 달라질 수 있는 것이다.
- 물론 모든 노드를 다 탐색해서, 각각의 노드를 시작점으로 해서 탐색해서 최단 경로를 찾아보겠다는 생각을 할 수도 있다. 같은 도착점을 향하는 경로가 두 개 있다고 했을 때, increasing numerical order에 따라 탐색한다고 가정해보자.
- 그렇다고 하더라도 비효율적일 수밖에 없다. 모든 노드가 시작점으로 고려가 되어야 하고, 모든 도착점 역시 시작점으로 고려되어야 하기 때문이다. 따라서 이러한 경우에는 O(노드 개수)²이 되기 때문에 비효율적이라고 볼 수 있다. BFS는 O(노드 개수 + 간선 개수) 만에 구할 수 있기 때문이다. 참고 링크
- 이 외에도 stack을 사용하는 DFS에 비해, BFS는 queue나 deque를 사용하므로 비교적 stack overflow 문제에서 자유롭게 공간을 활용할 수 있어, 넓은 범위를 탐색할 수 있다는 이점도 있다.
Point 2. 가중치가 있는 그래프에서 DFS와 BFS를 사용할 수 있는 이유
우리는 가중치가 없는 그래프인 경우 BFS를 사용할 수 있다는 것을 익히 알고 있다. 이 부분에 대해 궁금하다면 다음 링크를 참조하면 도움이 될 것이다. 이와 함께 간선에 가중치가 존재한다면 BFS를 사용할 수 없다는 것도 익히 알려진 사실이다. 단순히 depth로만 최단 거리가 정해지는 것이 아니기 때문이다. 같은 depth(층위)에 있는 노드끼리 이동하는 것은 고려하지 않는다.
예를 들어, A가 B와 C와 연결되어 있고 B와 C가 서로 연결되어 있다고 하자. 그렇다면 노드 A는 depth가 1이고, B, C는 depth가 2가 된다. A-B가 가중치 3, A-C가 가중치 1, B-C가 가중치 1라고 가정하자. 노드 B로 가는 최단 경로는 무엇일까? depth를 기준으로 하면 노드 A -> 노드 C가 된다. 하지만 이는 가중치를 고려하지 않은 경우이다. weight을 고려하면 노드 A -> 노드 C -> 노드 B가 가중치를 가장 적게 고려하는 경우가 되지만, depth를 기준으로 탐색하는 BFS에서는 해당 경로가 고려되지 않는다.
가중치가 존재할 때 DFS를 사용할 수는 없을까? 이 부분에 대한 정답도 마찬가지이다. 한 번 방문한 노드는 별도의 array에 방문처리를 하여 재방문하지 않는다. 물론, DFS를 사용하여 모든 간선을 전부 돌아보게 하면 가중치를 전체 고려할 수 있을 것이다. 하지만 이러한 경우에는 효율성이 지나치게 떨어진다. 아래 코드를 보자.
// https://stackoverflow.com/questions/36869226/find-all-paths-between-two-nodes-using-dfs-in-weighted-directed-graph def find_paths(self, start, end, weight_limit=10):
res = [] def dfs(start, end, path=[], weight=0):
path = path + [start]
if len(path) > 1:
weight += self.weights[(path[-2], start)]
if weight > weight_limit:
return []
if start == end:
res.append((path, weight))
return [path]
if start not in self.adjacent:
return []
paths = []
for node in self.adjacent[start]:
if node not in path:
paths.extend(dfs(node, end, path, weight))
return paths dfs(start, end)
return res
탐색해야 하는 경로가 정점의 수에 따라 팩토리얼로 증가한다. Fully connected graph를 가정한다면, 정점의 수가 n개일 때 탐색해야 하는 경로의 수는 n!이다. O(n!)이라는 것은 너무 많은 시간복잡도와 공간복잡도를 차지할 것이라고 쉽게 추측할 수 있다.
Point 3. 가중치가 있는 그래프에서 다익스트라 알고리즘을 쓰는 이유
가중치가 있는 그래프에서 BFS를 사용할 수 없는 이유는, BFS가 Greedy한 알고리즘이 아니기 때문이다. 이와 달리, 다익스트라 알고리즘은 Greedy하다. 그리디한 이유는 최소 거리에 최소 거리를 붙이면 최소 거리가 될 것이다라는 논리가 함축되어 있기 때문이다. 그래서 우리는 다익스트라 알고리즘이 최소 거리를 보증한다는 것을 귀류법으로 증명해보고자 한다. 참고 링크 참고 링크 2
- 가설: 이미 선택된 노드는 최단 거리가 갱신되지 않는다. 즉, 다익스트라 알고리즘으로 선택된 노드는 최종 최소 비용이다.
- 가. 이미 선택된 노드는 앞으로 선택되는 노드에 의해서 최단 거리가 갱신이 된다라고 가정한다. 즉, 이후 선택하는 노드를 거쳐 들어오는 더 짧은 최단 경로가 존재한다.
- 나. 만일 그러한 노드가 존재한다면, 해당 노드는 적어도 한 번 다익스트라 알고리즘을 이용해 거쳐온 노드 외의 노드를 지나야만 한다. 다익스트라 알고리즘으로 선택되어진 모든 노드만을 거쳐서 지나온다면, 해당 노드는 다익스트라 알고리즘으로 선택된 노드의 최소 비용을 갱신할 수 없기 때문이다.
- 다. 위의 (가)와 (나) 단계는 모순이다. 다익스트라 알고리즘은 분명 매번 최소 비용을 갖는 노드만을 선택한다고 하였는데, 그것보다 더 짧은 비용을 갖는 노드가 존재한다고하면 당연히 모순이다.
- 결론: 초기에 설정한 가정(이미 선택된 노드는 앞으로 선택되는 정점에 의해서 최단 거리가 갱신이 된다)은 모순이다. 즉, 귀류 가정이 모순이므로, 본 명제는 참이다.
다익스트라 알고리즘은 우선순위 큐를 이용하여 현재 시점에서 가장 거리가 짧은 간선을 선택한다. 우선순위 큐를 구현하기 위해서 최소 이진 힙(Min Binary Heap)을 주로 이용한다. 우선순위 큐를 사용할 때 시간 복잡도는 어떻게 될까. 다익스트라 알고리즘은 크게 1) 각 정점마다 인접한 간선을 모두 검사하는 작업을 진행하고 2) 우선순위 큐에 정점을 삽입하고 삭제하는 작업을 진행한다. 모든 간선을 검사하는 비용은 O(|간선의 개수|)만큼 들어가며, 이진 힙에서 원소를 추가하거나 삭제하는 비용은 O(log|정점의 개수|)가 된다. 따라서 이 두개를 곱하면 O(|간선의 개수| x log|정점의 개수|)가 된다. 따라서 O(vlog(E))가 된다.
다익스트라 알고리즘은 가중치가 음수인 경우에 사용할 수 없다고 한다. 그 이유는 가중치가 음수라면 최소 비용을 매번 갖는 노드보다 더 짧은 비용을 갖는 노드가 존재할 수 있기 때문이다. 가중치가 0보다 크다면, 간선을 통과하는 모든 경우에 비용이 증가하거나 같을 수밖에 없다. 하지만 음수라면 간선을 통과할 때 무조건 감소하게 된다. Ref 1 음수 가중치를 이용할 때는 벨만 포드 알고리즘을 사용해야 한다. 이는 기회가 된다면 나중에 소개해보도록 하겠다.
Point 4. 가중치가 0과 1만 존재하는 그래프에서 BFS를 쓰는 이유
어느 임의의 그래프에서 간선 (u, v)를 지난다고 가정해보자. 가중치가 0과 1만 존재하므로, 우리는 간선 (u, v)를 지날 때 노드 u와 v에 대해 다음의 사항을 고려할 수 있다. 참고 링크 참고 링크 2
- v는 u와 같은 레벨이다. 즉, 가중치가 0이라는 것은 v는 u와 같은 레벨이다.
- v는 u의 1레벨 아래이다. 즉, 가중치가 1이라는 것은 v는 u의 1레벨 아래이다.
우리가 노드 u에 있을 때, queue에는 level이 L[u] 또는 L[u] + 1 이라는 두 가지의 사항만 포함되어 있다는 사실을 알 수 있다. 임의의 u∈Q에 대하여 d[v]≤d[u]≤d[v]+1 가 성립한다는 것을 알고 있다. 큐에 u가 존재하는데, 해당 u가 d[u]−d[v]>1라고 가정해보자. 이 때 u는 또 다른 임의의 정점 t에 의하여 d[t]≥d[u]−1>d[v]가 성립되어야 한다. 하지만 이는 성립하지 않는다. 다익스트라 알고리즘은 오름차순으로 정점을 방문하기 때문이다. 따라서 귀류 명제가 거짓이므로 원 명제가 참이라고 할 수 있다.
큐에는 Q=v⏟_d[v],…,u⏟_d[v],m⏟_d[v]+1…n⏟_d[v]+1 가 들어가 있다고 볼 수 있다. 간선 (u, v)를 통과했을 때, 노드 v의 최단거리가 단축되었다면 deque의 앞 부분에 넣어준다. 노드 u와 같은 레벨이라면 deque의 뒷 부분에 넣어준다. queue가 총 2가지 필요한 데, 가중치가 +0 이거나 가중치가 +1인 경우 두 개에 따라 별도로 queue를 마련한다. deque가 있다면 앞에 넣거나 뒤에 넣으면 된다.
시간 복잡도는 어떻게 될까?
- deque에는 최대 O(V)개의 정점이 들어가게 된다. 그러므로 while문은 O(V)번 반복하게 된다.
- deque에서 pop을 하는것은 O(1)안에 완료된다. while문 안에 있는 for문은 deque에서 추출한 정점과 인접한 모든 정점의 개수만큼 반복된다. O(E)번 반복된다. if-else문은 O(1)안에 완료된다.
- O(V) * { O(1) + O(E) + O(1) }
= O(V) + O(V * E) + O(V) - (V * E) 는 전체 간선의 개수와 같다. 따라서,
O(2V) + O(E)
= O(V) + O(E)
= O(V + E)
문제 하나를 예시로 들어보자. 백준의 9376번 탈옥 문제이다.
# https://github.com/jypthemiracle/algorithm_log/commit/7f50fca6d47e134bf408f8616cd288c4ee31e854from collections import dequedx = [0,0,1,-1]
dy = [1,-1,0,0]def bfs(a, x, y):
n = len(a)
m = len(a[0])
dist = [[-1]*m for _ in range(n)]
q = deque()
q.append((x,y))
dist[x][y] = 0
while q:
x,y = q.popleft()
for k in range(4):
nx,ny = x+dx[k], y+dy[k]
if 0 <= nx < n and 0 <= ny < m and dist[nx][ny] == -1 and a[nx][ny] != '*':
if a[nx][ny] == '#':
dist[nx][ny] = dist[x][y] + 1
q.append((nx,ny))
else:
dist[nx][ny] = dist[x][y]
q.appendleft((nx,ny))
return distt = int(input())
for _ in range(t):
n,m = map(int,input().split())
a = ['.'+input()+'.' for _ in range(n)]
n += 2
m += 2
a = ['.'*m] + a + ['.'*m]
d0 = bfs(a, 0, 0)
x1=y1=x2=y2=-1
for i in range(n):
for j in range(m):
if a[i][j] == '$':
if x1 == -1:
x1,y1 = i,j
else:
x2,y2 = i,j
d1 = bfs(a,x1,y1)
d2 = bfs(a,x2,y2)
ans = n*mfor i in range(n):
for j in range(m):
if a[i][j] == '*':
continue
if d0[i][j] == -1 or d1[i][j] == -1 or d2[i][j] == -1:
continue
cur = d0[i][j] + d1[i][j] + d2[i][j]
if a[i][j] == '#':
cur -= 2
ans = min(ans,cur)
print(ans)
여기서의 아이디어는 수감자를 탈옥시키는 것을 조력해줄 때 상대방이 바깥에서 들어오면서 문을 최소한으로 열어야 하는데, 문을 여는 경우를 가중치 1이라고 할당하고 열지 않아도 되는 경우를 0이라 하는 것이다. 이 때 가중치가 0, 1 뿐이므로 0–1 BFS를 활용하여 문제를 풀 수 있는 것이다. 이 때 최소값을 구하면 문을 열어야 하는 최소 횟수를 구할 수 있다. 코드에서 보면 문이 있는 ‘#’ 의 표시가 있는 경우에는 deque의 오른쪽에 넣어주고, 그렇지 않은 경우에는 deque의 왼쪽에 넣어주어 서로 정렬이 되도록 했다.
