최단 거리 알고리즘

오늘은 코딩 테스트에서 간간히 나오는 최단 거리 알고리즘에 대해서 다루어보겠습니다.
최단 거리 알고리즘은 여러가지가 있지만, 이번 포스트는 대표적인 알고리즘 2개를 위주로 다루어보겠습니다. ^^

✊ Dijkstra

다익스트라 알고리즘으로 "시작점에서 나머지 점까지 가는 최단 거리" 를 구해주는 알고리즘 입니다.

구현 방법을 시간 복잡도에 따라 나누어 크게 2가지로 나눌 수 있습니다.
O(N^2) 과 O(ElogV)가 있는데, 전자는 구현이 비교적 간단하지만, 입력이 1만개 이하일 경우 사용 가능하고, 그 이상에는 후자로 이용해야 합니다.
이번 포스트에서는 그래서 어느 상황서나 사용 가능한 후자 코드를 구현해보겠습니다.

해당 시간 복잡도를 위해서는 우선순위 큐를 활용해서 구현하였고 코드는 아래와 같습니다.

import heapq # 시간 복잡도를 줄이기 위해서 우선순위 큐를 사용
import sys
INT_MAX = sys.maxsize

nodeCost, lineCost = tuple(map(int,input().split())) # 노드와 간선의 개수를 입력 받는 부분

graph = [[] for _ in range(nodeCost+1)] # 그래프에 정보를 기록할 리스트

k = int(input()) # 시작점을 입력 받는 부분 -> 다익스트라 알고리즘은 시작점 설정이 필수적

save = [] # 각 상황에서 다음 노드를 선택하기 위해 사용되는 우선순위 큐

result = [INT_MAX for _ in range(nodeCost + 1)] # 시작점에서 각 노드까지의 최단 거리 값을 담을 리스트

for _ in range(lineCost): # 간선에 대한 정보를 입력 받을 부분(리스트 활용)
    start, end, value = tuple(map(int,input().split()))
    graph[start].append((end, value))
    graph[end].append((start,value)) # 양방향 이라면 추가해주어야하는 코드 -> 단방향이면 해당 부분 주석 처리

heapq.heappush(save,(0,k)) # 시작 점의 값을 갱신
result[k] = 0

while save: # 최소값을 갱신해주는 과정은 우선순위 큐가 비었을 때, 중지
    min_value, min_idx = heapq.heappop(save) # 현재 큐에서 가장 짧은 거리를 선택

    # 해당 if 문 매우 중요@@@@@@!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
    if min_value != result[min_idx]: # 결과 리스트에 값이 있단는 것은 이미 최단 경로가 갱신되었다는 의미
        continue                     # 따라서 비교 후, 다르다면 넘겨주어야 함 -> 해당 코드가 없으면 시간 복잡도 증가
    
    for checkEnd, checkValue in graph[min_idx]: # 현재 점에서 갈 수 있는 도착점과 간선에 대한 정보를 뽑아내기
        newValue = checkValue + result[min_idx] # 현재 점을 거쳐서 가는 도착점까지의 거리를 계산
        if result[checkEnd] > newValue: # 기존의 최소값이 더 크다면,
            result[checkEnd] = newValue # 최소값을 갱신
            heapq.heappush(save,(newValue,checkEnd)) # 해당 변경상황을 큐에 저장

print(result) # 구해진 최단 거리들을 출력(인덴스 0은 무시)

해당 코드는 되도록 흐름을 암기해서 어떤 경우에도 사용할 수 있도록 준비할 수 있는 것이 좋겠습니다.

그 외에도 여러가지 스킬을 적용해볼 수 있습니다.

먼저, 문제에서 조건을 시작점을 정해주는 것이 아니라, 도착점을 알려주고, 나머지 점에서 도착점까지의 최단 거리를 구하라는 문제를 줄 경우입니다.
해당 경우는 단순하게 생각해서 양방향 그래프일 경우는 도착점을 시작점으로 생각해주고 다익스트라 알고리즘을 적용하면 되지만, 단방향일 경우는 간선을 입력 받을 때, 도착점과 시작점을 바꾸어서 입력을 받고, 도착점을 시작점으로 해서 다익스트라 알고리즘을 구해주면 원하는 답을 얻으실 수 있습니다.

다음으로는 시작점에서 특정 도착점까지의 최단 거리 경로를 구하는 경우입니다.
해당 경우는 리스트를 추가해주어야 합니다.
리스트를 추가해주고, 점이 갱신될 때마다, 해당 점까지의 바로 직전 노드를 리스트에 기록하고 이를 활용하면 원하는 답을 얻을 수 있습니다.
관련 코드는 아래를 참고하시면 됩니다.

if result[checkEnd] > newValue: # 기존의 최소값이 더 크다면,
	result[checkEnd] = newValue # 최소값을 갱신
   	heapq.heappush(save,(newValue,checkEnd)) # 해당 변경상황을 큐에 저장
    
    path[checkEnd] = min_idx # 최소값을 갱신할 때, 직전 노드도 갱신
    
# 만약, 최단 경로를 원하는 도착점을 k,시작점을 w라 두면,
way = []
way.append(k)
# 도착점부터 거슬러 올라가서 시작점이 나올 때까지 경로 검색해주기
while k != w:
	k = path[k]
    way.append(k)
# 위에서 구해진 way가 거꾸로된 최단 경로로 이를 거꾸로 출력하면 결과가 나옴
for i in way[::-1]:
	print(i,end=" ")
    

마지막으로, 동일한 최단 거리를 가지는 경로들이 존재하는 경우 다음 노드의 숫자가 가장 작은 경우를 선택하는 문제입니다.
즉, 현재 위치에서 최단 경로로 이동할 수 있는 방법이 여러 가지인 경우입니다.
예를 들어 1->4->5 와 1->2->6->5 인 경우, 후자를 선택하는 것입니다.
이를 위해서는 먼저 간선을 뒤집어서 그래프를 만들고, 시작점과 도착점을 바꾸어서 다익스트라 알고리즘을 구현하는 것이 중요합니다.
해당 과정을 통해 최단 거리를 구했다면, 정상적인 그래프 기준으로 시작점에서 출발해서 도착점까지의 거리를 순차적으로 구해줍니다.
관련 코드는 아래와 같습니다.

# 도착점을 k, 시작점을 w라 가정
# 노드의 개수는 n
# 거꾸로 그래프를 뒤집어서 최단 경로를 구한 것이 있다고 가정(result)
# 여기서 나오는 graph 도 뒤집어진 그래프임을 명심
print(w,end=" ") # 먼저 시작점을 출력
while w != k:
	for i in range(1,n+1):
    	if graph[i][w] == 0: # 그래프를 거꾸로 보았을 때, 해당 점에서 w까지 경로가 있는지 판단
        	continue # 없다면 바로 다음 i로 넘어가기
       	if result[i] + graph[i][w] == result[w]: # 만일 거꾸로 했을 때, 갈 수 있으면 계산
        	w = i # 갈 수 있다면 그 점을 다음 노드로 선택
            break
    print(w, end=" ") # 경로를 구해지는 대로 출력	

👊 Floyd Warshall

다익스트라가 시작점을 고정하고 나머지 노드까지의 최단 거리를 알고 싶을 때 유용하다면, 시작점이나 도착점을 정하지 않고, 모든 지점의 점을 알고 싶은 경우에는 플로이드 워셜 알고리즘을 자주 사용합니다.

플로이드 워셜 알고리즘은 O(N^3)의 시간 복잡도를 가지지만, 다익스트라에서 해당 과정을 반복하는 경우에도 비슷하거나 혹은 더 심한 시간 복잡도가 나올 수 있으므로, 위에서 언급한 특정 경우에는 오히려 다익스트라보다 유용하게 사용될 수 있음을 명심해야됩니다.

코드는 오히려 다익스트라 알고리즘에 비하면 굉장히 간단합니다.

import sys
INT_MAX = sys.maxsize


node, line = tuple(map(int,input().split())) # 노드와 간선의 정보를 입력 받는 부분

result = [[INT_MAX]*(node + 1) for _ in range(node + 1)] # 결과를 담을 변수를 설정(여기에 간선 값과 결과를 전부 저장)

for i in range(1,node + 1):
    result[i][i] = 0 # 각 노드의 자기자신은 최단 거리를 0으로 미리 설정

for _ in range(line): # 간선에 대한 정보를 입력 받는 부분
    start, end, distance = tuple(map(int, input().split()))
    result[start][end] = distance 
    result[end][start] = distance # 그래프가 양방향 그래프인 경우 -> 단방향이면 해당 부분 주석처리
    # 참고로 두 노드를 연결하는 간선이 여러개 주어질 수 있다면 아래와 같이 코드 구현
    #result[start][end] = min(result[start][end],distance) 

# 플로이드 워셜의 핵심 코드 -> 아래 부분은 기계적으로 암기!!!!!!!!!!
for k in range(1,node+1):
    for i in range(1, node+1):
        for j in range(1, node+1):
            # 바로 가는게 짧은지, 아니면 특정 k를 거쳐서 가는게 빠른지 비교 후 기록
            result[i][j] = min(result[i][j],result[i][k] + result[k][j])

# 최단 거리를 행렬로 출력
for i in range(1, node +1):
    for j in range(1, node+1):
        if result[i][j] == INT_MAX:
            print(-1,end=" ")
        else:
            print(result[i][j], end=" ")
    print()

핵심은 제가 중간에 주석으로 표시한 부분이 핵심이고, 이 부분은 암기하는 것이 굉장히 좋겠습니다.

이를 응용한 것으로는 시작점과 도착점을 지정하고 두 점 사이에 경로가 있는지 없는지 여부를 판단하는 것을 할 수 있습니다.
왜냐하면 ,플로이드 워셜 알고리즘은 모든 경우의 수를 파악해서 진행하기 때문에 그 과정에서 코드를 조금만 변형하면 두 점 사이에 경로가 있는지 없는지 여부를 파악할 수 있는 것입니다.
관련 코드는 아래와 같습니다.

# 그래프는 아까와 달리 0으로 초기화해줍니다.(경로 없음 = 0, 경로 있음 = 1)
result = [[0] * (node + 1) for _ in range(node+1)]
for i in range(1,line+1):
	start, end = tuple(map(int,input().split()))
    result[start][end] = 1 # 경로가 존재하면 1
for i in range(1, node + 1):
	result[i][i] = 1 # 자기자신은 당연히 갈 수 있으므로 모두 1로 처리
for k in range(1,node + 1):
	for i in range(1,node + 1):
    	for j in range(1,node + 1):
        	if result[i][k] and result[k][j]: # 해당 조건을 만족하면,
            	result[i][j] = 1 # 해당 경로가 있다는 것으로 인지되므로 1로 처리
for i in range(1, node+1):
	for j in range(1, node+1):
    	print(reuslt[i][j], end=" ")
    print()