[알고리즘 정리] 다익스트라 !

Intro

처음 다익스트라를 접한 상황

 
다익스트라를 처음 접했다면 대부분 이런 상황일 것이다.
처음에는 너무 복잡해 보여서 이게 어떻게 돌아가는 거지..? 했는데, 계속 파보다 보니 최단거리를 구하는 하나의 템플릿 느낌이었다. 더 자세히 말하자면, 현 시점에서 파악한 최단 경로에서, 더 짧은 최단 경로를 발견하면 이를 갱신하는 것이다.

 

내가 위에서 '템플릿' 이라고 했는데,, 다익스트라 문제를 많이 풀어보지 않아서 자세히는 모르지만,
최단경로를 구하는 코드를 통째로 파악해서 코테에서 다익스트라 문제를 맞닥뜨렸을 때 꽁으로 가져가는 문제라고 한다..ㅎ
그래도 본질적인 코드를 이해하는 것이 중요하니 하나하나 짚어보자.

---

아래는 다익스트라로 최단 경로를 구하는 코드이다. 아래에서 하나하나 살펴 보겠다.

def dijkstra(start, n, A):
    dist = [INF] * (n + 1)
    dist[start] = 0
    queue = [(0, start)]

    while queue:
        cost, idx = heappop(queue)
        if dist[idx] < cost:
            continue

        for adj, s in A[idx]:
            if dist[adj] > cost + s:
                dist[adj] = cost + s
                heappush(queue, (dist[adj], adj))

    return dist

 
 

1. 인접 리스트로 그래프 구현

다음과 같은 그래프를 인접 리스트로 구현하자. (노드, 가중치)
 
 

 
[코드]

A = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b, c = map(int, input().split())  # a, b: 정점, c: 거리
    A[a].append((b, c))
    A[b].append((a, c))

 

다익스트라 알고리즘은 시간 복잡도 측면에서 N의 크기가 클 것을 대비해 인접 리스트를 선택하여 구현하는 것이 좋다.

 

2. 최단 거리 리스트 초기화

최단 거리 리스트를 만들고 출발 노드는 0, 이외의 노드는 무한으로 초기화한다.
무한대는 float('inf') 로 설정할 수 있다.
 

[코드]

INF = float('inf')  # 초기 거리 값을 무한대로 세팅

def dijkstra(start):
    dist = [INF] * (n + 1)  # 각 정점까지의 최단거리 저장
    dist[start] = 0         # 출발 노드
    
...

 

3. 값이 가장 작은 노드 고르기

최단 거리 리스트에서 현재 값이 가장 작은 노드를 고른다.
여기서는 값이 0인 출발 노드에서 시작하면 된다.
 

[코드]

def dijkstra(start):

...

	queue = [(0, start)]

    # 큐에서 가장 짧은 거리의 정점을 꺼내서 인접한 정점들로의 거리 갱신
    # 출발 노드 부터 시작 !
    while queue:
        cost, u = heappop(queue)
        
...

 

4. 최단 거리 리스트 업데이트 하기

선택된 노드에 연결된 에지의 값을 바탕으로 다른 노드의 값을 업데이트 한다.
앞서 저장한 연결 리스트를 이용해 현재 선택된 노드의 에지들을 탐색하고 업데이트 하면 된다.
연결 노드의 최단 거리는 값들 중 더 작은 값으로 업데이트 한다.
 

[코드]

def dijkstra(start):

...

        for adj, d in A[u]:
            if dist[adj] > cost + d:
                dist[adj] = cost + d
                heappush(queue, (dist[adj], adj))  # 거리 갱신

    return dist

 


위의 3~4 과정을 반복하면 최단 거리 리스트가 완성된다.

 

 

---

내가 푼 다익스트라 문제

 

다시 한 번 정리하면 다익스트라 알고리즘은 출발 노드와 그 외 노드 간의 최단 거리를 구하는 알고리즘이다.

 

되게 복잡해 보이고 실제로도 되게 복잡하지만, 문제를 많이 풀다 보면 익숙해질 거라 믿는다,,

그리고 구현 코드가 거의 정해져 있는 데다가, 가끔 코테 문제로 나올 때가 있다 하니 꼭 숙지하도록 하자!

 

아래는 대표적인 다익스트라 백준 문제이다.

 

• 특정한 최단 경로
• 해킹
• 최소 비용 구하기
• 녹색 옷 입은 애가 젤다지?
• 알고스팟
• 파티