[Algorithm] 다익스트라 알고리즘(Dijkstra’s Algorithm)

1. 백준 1916번 문제
2. 다익스트라 알고리즘(Dijkstra’s Algorithm)

1. 백준 1916번 문제

백준 1916

 

오늘도 알고리즘 공부를 위해 백준 문제에 도전했는데, 1916번 문제인 "최소비용 구하기"에 도전했습니다. 처음에는 간단하게 DFS를 이용하려 했지만, 최대 도시의 수가 100,000개로 주어지고 시간 제한이 0.5초라는 점을 고려하니 다른 접근 방식이 필요하다고 느꼈습니다. 문제에서 어떤 간선에는 큰 값이 들어갈 수도 있고 작은 값이 들어갈 수도 있다는 점을 고려하면, 결국에는 모든 경우를 탐색해야 한다고 생각했습니다. 그러나 시간 제한이 짧기 때문에 조건을 걸어주어 조기에 탐색을 종료할 수 있도록 백트래킹을 이용하여 코드를 작성했습니다.

 

import sys
sys.setrecursionlimit(100001)

n=int(sys.stdin.readline().rstrip())
m=int(sys.stdin.readline().rstrip())

graph=[[]for _ in range(n+1)]
visited=[0]*(n+1)
arr=[]

for i in range(m):
    start, end, weight=map(int,sys.stdin.readline().split())

    graph[start].append([end,weight])

start,end=map(int,sys.stdin.readline().split())

max=0
def dfs(start,weight):
    global max

    if max!=0 and max<weight:
        return

    if start==end:
        max = weight
        return

    for i in graph[start]:
        if visited[i[0]]==0 or visited[i[0]] > i[1]+weight:
            visited[i[0]]=i[1]+weight
            dfs(i[0],visited[i[0]])

dfs(start,0)

print(max)

 

코드는 조금 지저분했지만, 입력과 출력은 정확하여 그대로 제출했더니 시간 초과 결과가 나왔습니다. 특히 2% 부분에서 시간 초과가 발생했는데, 이를 해결하기 위해 다른 알고리즘을 적용해야 한다는 것을 깨달았습니다. 그러나 정답을 찾지 못해서 질문 게시판을 통해 다익스트라 알고리즘을 사용해야 한다는 조언을 얻었습니다.

 

2. 다익스트라 알고리즘(Dijkstra’s Algorithm)

1) 정의

• DP를 활용한 최단경로 탐색 알고리즘
• 최단 거리는 여러개의 최단 거리로 이루어져 있기 때문에 DP
  (작은 문제가 큰 문제의 부분집합에 속해있지만, 두 문제가 같은 모양이 아니기 때문에 분할 정복이 아님)
• 음의 간선 포함할 수 없음
• 특정 지점으로부터 최단 거리를 계산할 때 유용
• for문으로 구현할 수 있지만 heap으로 구현하면

 

2) 원리

 

(1) 출발 노드를 설정

(2) 최단 거리 테이블 초기화(무한으로 설정 / INF=int(1e9) )
( int(1e9) 는 10억으로 충분히 큰 수이고, 한 번 자기 자신을 더하였을 때 int형의 범위를 넘지 않습니다. )

(3) 방문하지 않은 노드 중에 최단 거리 테이블에서 최단 거리가 가장 짧은 노드를 선택

(4) 선택한 노드를 거쳐 다른 노드로 가는 거리를 계산

(5) 계산된 거리가 최단 거리 테이블의 거리보다 짧을 경우, 갱신

(6) 위의 3,4,5 를 반복

 

단순히 현재 노드와 이동 가능한 다음 노드와으 거리를 기준으로 거리를 계산하는 것이 아니라 heap에 저장된 거리를 기준으로 순서가 발생한다는 점에 유의해야합니다. 또한, 거리가 입력된 노드 중 최단거리가 가장 작은 노드를 선택할 때 단순히 반복문으로 구현하면 시간복잡도가 비효율적입니다. 이를 heap으로 구현하면, 코드의 길이가 짧아지고 시간복잡도도 낮아집니다.

 

3) 코드

import sys
import heapq

INF=int(1e9)

n=int(sys.stdin.readline().rstrip())
m=int(sys.stdin.readline().rstrip())

graph=[[]for _ in range(n+1)]
distance=[INF]*(n+1)

for i in range(m):
    start,end,weight=map(int,sys.stdin.readline().split())
    graph[start].append([end,weight])

start,end=map(int,sys.stdin.readline().split())

def dijkstra(start):
    heap=[]
    distance[start]=0

    heapq.heappush(heap,(0,start))

    while heap:
        print(heap)
        weight,node=heapq.heappop(heap)

        if distance[node] < weight: # 이미 입력되어있는 값이 현재노드까지의 거리보다 작다면 이미 방문한 노드이기에 넘어간다.
            continue

        for i in graph[node]:
            next_val=i[1]+weight

            if next_val < distance[i[0]]:
                distance[i[0]]=next_val
                heapq.heappush(heap,(next_val,i[0]))

dijkstra(start)

print(distance[end])

 

처음 코드를 작성할 때 주석 처리한 if 문에 대해 이해가 되지 않았습니다. 왜냐하면 heap에 값이 들어오기 위해서는 "next_val < distance[i[0]]" 이라는 조건을 통과해야 하는데, 이 조건을 통과하고 나서 저장되는 (next_val, i[0]) 값이 위에서 pop 되고 if 문에 오면 distance[node], weight 두 가지 값은 항상 같은 값을 가지게 되니까 if 문에 걸릴 일이 없는거 아닌가? 라는 생각이 들었습니다. 주석에 적힌 "이미 입력된 값이 현재 노드까지의 거리보다 작다면 continue를 하면 된다" 라는 말은 이해했지만, 코드 상에서 저렇게 작성된다는 것이 이해되지 않아 한참을 고민했습니다. 그러다가 heap 값을 찍어보면서 해답을 찾았습니다.

단계별 heap

 

heap에 한 번 들어온 값은 변경되지 않지만, distance의 값은 아래 반복문에서 더 나은 경로가 발견되면 갱신될 수 있다는 사실을 간과한 것이었습니다. 예를 들어, 문제의 예제를 살펴보면, 1번 노드에서 5번 노드로 10의 비용으로 이동할 수 있기 때문에 distance[5]에는 10이 들어가고, heap에는 (10, 5)의 값이 저장됩니다. 그러나 그 이후에 1->4->5로 가는 경로를 통해 4의 비용으로 10보다 더 적은 비용으로 5번 노드에 도달할 수 있게 되었고, distance[5]에는 4의 값이 갱신됩니다. 그러나 heap에는 이미 (10, 5)의 값이 남아 있고, 이 값이 if 문에 걸리게 됩니다. 따라서 이런경우에 continue 문이 실행되면서 시간을 절약할 수 있게 되는 것이었습니다.

 

 

참고자료

https://dmaolon00.tistory.com/entry/AlgorithmPython-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EC%B5%9C%EB%8B%A8-%EA%B2%BD%EB%A1%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%B4%EB%9E%80-dijkstra

https://c4u-rdav.tistory.com/50