[알고리즘] 다익스트라 & 프림 최최최최종 복습하기

그래프 상에서 노드 간의 탐색 비용을 최소화하는 알고리즘인 최단 거리 알고리즘...

맨날 쓰고 까먹고 쓰고 까먹고의 반복. 이번이 "최최최최종"이 되길.

 

1 Dijkstra + 우선순위 큐

2 Bellman-Ford

3 Floyd-Warshall

 

MST 구하는 알고리즘

 

4 Prim - 정점 기준 + 우선순위 큐

5 Kruskal - 간선 기준

 

 

1 다익스트라 알고리즘

특정 하나의 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘.

Greedy + DP 형태. 음의 가중치가 있다면 사용 못함.

 

중요한 건 뭐냐면, 최적화 안된 형태의 다익스트라는 시간복잡도가 벨만포드보다 빠르다고 할 수 없다.

우리가 말하는 다익스트라가 빠르다는 건 그러니까, heap을 활용해서 우선순위 큐를 쓰는 최적화된 버전에 대한 설명인 것.

 

1️⃣ 다익스트라 알고리즘의 기본 형태

---

🚀 기본적인 다익스트라 알고리즘 (비효율적인 O(V²) 버전)

• 방법: visited(set) 사용 + 배열을 이용한 선형 탐색
• 핵심 동작:
  1. 시작 정점 S의 최단 거리를 0으로 설정, 나머지는 ∞
  2. 방문하지 않은 정점 중에서 최단 거리 정점을 찾음 → O(V) (선형 탐색)
  3. 해당 정점을 방문 처리하고, 이웃 노드의 거리 갱신
  4. ②~③을 모든 정점(V)만큼 반복 → O(V²)

 

---

🚀 기본 버전의 문제점

• 최단 거리 정점을 찾는 데 O(V) 시간이 걸림
• 전체적으로 O(V²)의 복잡도가 발생
• V가 클 경우 비효율적 (예: V = 10,000이면 100,000,000번 연산!)

---

2️⃣ 다익스트라 알고리즘의 최적화된 형태

---

🔥 최적화된 다익스트라 (우선순위 큐 O((V+E) log V) 버전)

• 방법: 우선순위 큐(힙) 사용 + visited 제거 (if distances[current_node] < current_distance: continue 활용)
• 핵심 동작:
  1. 힙을 사용하여 최단 거리 노드를 빠르게 찾음 → O(log V)
  2. 간선 업데이트 시 힙에 다시 삽입 → O(log V)
  3. 모든 간선을 처리하며 V-1번 반복 → O((V+E) log V)

import heapq  # 우선순위 큐 사용

def dijkstra_optimized(graph, start):
    # 최단 거리 초기화
    distances = {node: float('inf') for node in graph}
    distances[start] = 0

    # 우선순위 큐 (힙) 초기화
    priority_queue = []
    heapq.heappush(priority_queue, (0, start))  # (거리, 노드)

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        # 이미 처리된 정점이면 스킵
        if distances[current_node] < current_distance:
            continue

        # 현재 정점의 모든 이웃 노드 탐색
        for neighbor, weight in graph[current_node].items():
            new_distance = current_distance + weight

            # 최단 거리 갱신
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance
                heapq.heappush(priority_queue, (new_distance, neighbor))

    return distances

---

🔥 최적화된 버전의 장점

• "최단 거리 정점 찾기"를 O(V)에서 O(log V)로 개선 (heapq.heappop())
• 총 시간 복잡도: O((V + E) log V)
• V가 커도 실행 가능! (예: V = 10,000일 때 연산 횟수 ≈ 130,000)

---

3️⃣ 기본 다익스트라 vs 최적화된 다익스트라 비교

---

구현 방식최단 거리 찾기 비용최단 거리 갱신 비용전체 시간 복잡도특징

배열(Array) 사용 (O(V²))	O(V) (선형 탐색)	O(1)	O(V²)	작은 그래프에서만 적합
우선순위 큐(힙) 사용 (O((V+E) log V))	O(log V) (힙)	O(log V)	O((V + E) log V)	빠르고 실용적

---

4️⃣ 정리

✅ 다익스트라의 기본 꼴

• 최단 거리 정점을 찾고, 이웃 노드를 업데이트하는 방식
• 기본 버전 (O(V²)): visited(set) 사용 + 선형 탐색
• 최적화된 버전 (O((V+E) log V)): 힙을 사용하여 visited 없이 continue로 처리

✅ 왜 힙을 쓰는가?

• 최단 거리 정점 찾기를 O(V) → O(log V)로 최적화
• 전체 시간 복잡도를 O(V²) → O((V + E) log V)로 줄임
• V가 커질수록 차이가 극명하게 벌어짐

✅ 결론: 다익스트라를 사용할 때는 무조건 힙을 쓰는 게 유리하다! 🚀

 

 

 

시간 복잡도는 다음과 같음.

 

 

 

다익스트라가 쓰이는 예시로는 아래의 사례들이 있음.

 

 

2 Prim + 우선순위 큐

 

 

 

최단거리 말고도 각종 BFS/ DFS 관련 프로그래머스 문제들 모음

 

https://school.programmers.co.kr/learn/courses/30/lessons/42861

https://school.programmers.co.kr/learn/courses/30/lessons/1844

https://school.programmers.co.kr/learn/courses/30/lessons/43162

https://school.programmers.co.kr/learn/courses/30/lessons/49189

https://school.programmers.co.kr/learn/courses/30/lessons/49191

https://school.programmers.co.kr/learn/courses/30/lessons/132266

https://school.programmers.co.kr/learn/courses/30/lessons/43163

https://school.programmers.co.kr/learn/courses/30/lessons/43164

 

 

진짜 중요한 것은,

 

1 가능하다면 visited 필수적으로 써야 한다는 것.

2 visited 등을 가능하면 queue에 추가하는 곳 (queue에서 꺼내는 곳 말고) 에서 써야 극단적으로 효율적이어짐.

3 DFS를 쓸때는 재귀를 쓸 이유가 없음. stack 활용 고고.