BFS를 이용한 완전 탐색
조건: 모든 간선의 가중치가 동일할 때
결과: 한 정점에서 다른 모든 정점까지의 거리
구현 방법 / 시간복잡도: 큐 / $O(V+E)$
간선에 가중치가 없거나 모두 동일한 경우 단순 탐색으로 $O(V+E)$만에 최단 경로를 찾을 수 있다.
from collections import deque
distances = [None] * V
queue = deque([0])
distances[0] = 0
while queue:
target = queue.popleft()
for next_target in graph[target]:
if distances[next_target] == None:
queue.append(next_target)
distances[next_target] = distances[target] + 1
print(*distances)graph는 인접 리스트로 구현된 그래프 정보이다.
0-1 BFS 알고리즘
조건: 모든 간선의 가중치가 0 또는 1일 때
결과: 한 정점에서 다른 모든 정점까지의 거리
구현 방법 / 시간복잡도: 덱 / $O(V+E)$
간선의 가중치가 0과 1 두 종류라면 큐 대신 덱을 이용해 $O(V+E)$만에 최단 경로를 찾을 수 있다.
방법은 간단하다: 가중치가 0이면 덱의 앞에, 1이면 덱의 뒤에 삽입하여 탐색하면 된다
(아래 다익스트라의 개념을 가져오되 우선순위 큐 없이 덱으로 구현했다고 보면 쉽다.)
from collections import deque
distances = [None] * V
dq = deque([0])
distances[0] = 0
while dq:
target = dq.popleft()
for next_target, weight in graph[target]:
if distances[next_target] == None:
if weight == 0: dq.appendleft(next_target)
else: dq.append(next_target)
distances[next_target] = distances[target] + weight
print(*distances)graph는 인접 리스트로 구현된 그래프 정보이다.
다익스트라(Dijkstra) 알고리즘
조건: 음수 간선이 없을 때
결과: 한 정점에서 다른 모든 정점까지의 거리
구현 방법 / 시간복잡도: BFS + 우선순위 큐 / $O(Elog_2E)$
우선순위 큐를 이용한 다익스트라 알고리즘은 현재까지 탐색한 간선 중 가장 가까운 간선부터 방문하며 최단 거리를 갱신한다.
import heapq
distances = [float("inf")] * V
heap = [(0, 0)]
distances[0] = 0
while heap:
now_distance, now_target = heapq.heappop(heap)
# 이미 now_distance보다 작은 거리를 탐색했으면 갱신 필요 X
if distances[now_target] < now_distance: continue
for next_target, weight in graph[now_target]:
next_distance = now_distance + weight
if next_distance < distances[next_target]:
distances[next_target] = next_distance
heapq.heappush(heap, (next_distance, next_target))
print(*distances)graph는 인접 리스트로 구현된 그래프 정보이다.
벨만-포드(Bellman-Ford) 알고리즘
결과: 한 정점에서 다른 모든 정점까지의 거리
구현 방법 / 시간복잡도: 모든 간선을 확인하며 최단거리 $V-1$번 갱신 / $O(VE)$
벨만-포드 알고리즘은 음수 간선이 존재해도 최단 거리를 구해낼 수 있으며, 음수 사이클의 존재 여부도 판별할 수 있다.
음수 사이클이 없는 경우 $V-1$번 반복만에 최단 거리를 구할 수 있으며, 이후에도 거리가 줄어드는(갱신되는) 경우 음수 사이클이 있는 것이다.
distances = [float("inf")] * V
distances[0] = 0
# V번 반복
for i in range(V):
for j in range(E):
now_node, next_node, distance = edges[j]
if distances[now_node] != float("inf") and distances[next_node] > distances[now_node] + distance:
distances[next_node] = distances[now_node] + distance
# V번째에도 갱신되었다면 사이클 있는 것.
if i == V - 1:
print("!!!! 사이클 발견 !!!!")
exit()
print(*distances)edges는 각 간선들의 (시작점, 끝점, 거리)를 저장해둔 리스트이다.
플로이드-워셜(Floyd-Warshall) 알고리즘
결과: 그래프 내 모든 정점끼리의 거리
구현 방법 / 시간복잡도: 모든 경유지에 대해 시작점과 도착점 탐색 / $O(V^3)$
플로이드-워셜 알고리즘은 음수 간선의 여부와 관계 없이 그래프 내 모든 정점끼리의 거리를 구할 수 있다.
다만 시간 복잡도가 크므로 문제에서 주어진 $V$의 크기를 꼭 확인하고 사용하자.
구현은 삼중 반복문을 사용해 $i$에서 $j$로 가는 데 $k$를 경유하는 것이 더 짧은 지를 계속 체크하면서 갱신해나가면 된다.
for k in range(V):
for i in range(V):
for j in range(V):
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
for i in range(V):
print(*graph[i])graph는 인접 행렬로 구현된 그래프 정보이다.
