[Python] Algorithm #07: 최단 경로와 그리디

최단 경로(Shortest Path)와 그리디(Greedy) 알고리즘의 기본 개념을 다룹니다.

 

최단 경로는 그래프에서 출발점부터 도착점까지의 비용이 가장 작은 경로를 찾는 문제입니다.

그리디는 매 순간 현재 상황에서 가장 좋아 보이는 선택을 하는 방법입니다.

두 주제는 서로 다른 알고리즘이지만, 문제의 조건을 분석하고 적절한 선택 기준을 세우는 것이 중요하다는 공통점이 있습니다.

---

Part 1. 최단 경로

1. 최단 경로 문제

그래프의 간선에 거리, 시간, 비용과 같은 가중치가 주어질 수 있습니다.

A --2-- B
|       |
5       1
|       |
C --1-- D

• 단순히 거치는 간선의 수가 가장 적은 경로가 아니라, 가중치의 합이 가장 작은 경로를 찾아야 합니다.

최단 경로 알고리즘은 그래프의 조건에 따라 달라집니다.

그래프 조건	사용할 수 있는 방법
모든 간선의 비용이 같음	BFS
음수가 없는 가중치	다익스트라
음수 간선이 존재	벨만-포드
모든 노드 사이의 최단 거리	플로이드-워셜

• 이번 글에서는 코딩테스트에서 자주 사용하는 다익스트라 알고리즘을 중심으로 다룹니다.

---

2. 다익스트라 알고리즘

다익스트라 알고리즘은 하나의 시작 노드에서 다른 모든 노드까지의 최단 거리를 구합니다.

 

단, 음수 가중치가 있는 그래프에는 사용할 수 없습니다.

 

다익스트라의 핵심 과정은 다음과 같습니다.

1. 시작 노드의 거리를 0으로 설정합니다.
2. 아직 처리하지 않은 노드 중 거리가 가장 짧은 노드를 선택합니다.
3. 선택한 노드를 거쳐 다른 노드로 가는 거리를 계산합니다.
4. 기존 거리보다 짧다면 값을 갱신합니다.
5. 모든 노드를 처리할 때까지 반복합니다.

 

거리 갱신 과정은 다음과 같이 표현할 수 있습니다.

새로운 거리 = 현재 노드까지의 거리 + 다음 간선의 비용

• 새로운 거리가 기존에 알고 있던 거리보다 짧다면 최단 거리를 갱신합니다.

---

3. 우선순위 큐

매번 거리가 가장 짧은 노드를 빠르게 선택하기 위해 우선순위 큐를 사용합니다.

 

Python에서는 heapq를 사용해 최소 힙을 구현할 수 있습니다.

import heapq

heap = []

heapq.heappush(heap, (3, "A"))
heapq.heappush(heap, (1, "B"))
heapq.heappush(heap, (2, "C"))

print(heapq.heappop(heap))  # (1, 'B')

• 튜플을 힙에 넣으면 첫 번째 값을 우선적으로 비교합니다.
• 따라서 (거리, 노드) 형태로 저장하면 거리가 가장 짧은 노드를 먼저 꺼낼 수 있습니다.

---

4. 다익스트라 구현

인접 리스트에는 (연결된 노드, 비용)을 저장합니다.

graph = [
    [],
    [(2, 2), (3, 5)],
    [(3, 1), (4, 2)],
    [(4, 1)],
    []
]

 

다익스트라 알고리즘은 다음과 같이 구현할 수 있습니다.

import heapq

INF = float("inf")

def dijkstra(graph, start):
    distance = [INF] * len(graph)
    distance[start] = 0

    heap = [(0, start)]

    while heap:
        current_distance, current = heapq.heappop(heap)

        if (distance[current] < current_distance):
            continue

        for next_node, cost in graph[current]:
            new_distance = current_distance + cost

            if (new_distance < distance[next_node]):
                distance[next_node] = new_distance
                heapq.heappush(heap, (new_distance, next_node))

    return distance

• distance[node]은 시작점에서 node까지 알려진 최단 거리를 의미합니다.
• 힙에서 꺼낸 거리가 이미 저장된 최단 거리보다 크다면 더 좋은 경로가 나중에 먼저 처리된 상태이므로 건너뜁니다.

---

5. 입력으로 그래프 만들기

방향 그래프의 입력을 받아 인접 리스트를 만들 수 있습니다.

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]

for _ in range(M):
    start, end, cost = map(int, input().split())
    graph[start].append((end, cost))

 

무방향 그래프라면 반대 방향의 간선도 추가합니다.

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

---

6. 시간복잡도

우선순위 큐를 사용하는 다익스트라 알고리즘의 시간복잡도는 일반적으로 O((V + E) log V) 또는 O(E log V)로 표현합니다.

• V: 노드의 수
• E: 간선의 수

각 간선을 확인하고, 거리 갱신이 발생하면 힙에 새로운 값을 추가합니다.

---

7. 최단 경로에서 경로 복원

거리뿐 아니라 실제로 어떤 노드를 거쳤는지 구해야 할 수도 있습니다.

 

최단 거리가 갱신될 때 이전 노드를 함께 저장합니다.

import heapq

INF = float("inf")

def dijkstra(graph, start):
    distance = [INF] * len(graph)
    previous = [-1] * len(graph)

    distance[start] = 0
    heap = [(0, start)]

    while heap:
        current_distance, current = heapq.heappop(heap)

        if (distance[current] < current_distance):
            continue

        for next_node, cost in graph[current]:
            new_distance = current_distance + cost

            if (new_distance < distance[next_node]):
                distance[next_node] = new_distance
                previous[next_node] = current
                heapq.heappush(heap, (new_distance, next_node))

    return distance, previous

 

도착점부터 previous를 따라가면 경로를 복원할 수 있습니다.

def restore_path(previous, target):
    path = []
    current = target

    while (current != -1):
        path.append(current)
        current = previous[current]

    return path[::-1]

---

8. 최단 경로의 주의점

• 간선의 비용이 모두 같은 문제라면 BFS가 더 단순합니다.
• 다익스트라는 음수 간선이 있을 때 사용할 수 없습니다.
• 방향 그래프와 무방향 그래프를 구분해야 합니다.
• 연결되지 않은 노드의 거리는 INF로 남습니다.
• 힙에 (노드, 거리)가 아니라 (거리, 노드) 순서로 넣어야 합니다.
• 힙에 남아 있는 오래된 거리 정보를 건너뛰는 조건이 필요합니다.

---

Part 2. 그리디

9. 그리디 알고리즘이란?

그리디 알고리즘은 각 단계에서 현재 가장 좋아 보이는 선택을 합니다.

 

전체 경우를 모두 확인하지 않기 때문에 빠르게 답을 구할 수 있지만, 모든 문제에서 최적의 답을 보장하지는 않습니다.

따라서 단순히 최댓값이나 최솟값을 계속 선택하는 것이 아니라, 그 선택이 최종적으로도 최적해를 만든다는 근거가 필요합니다.

---

10. 거스름돈 예제

500원, 100원, 50원, 10원 동전으로 거스름돈을 줄 때 동전 개수를 최소화해보겠습니다.

 

가장 큰 동전부터 최대한 많이 사용합니다.

def count_coins(amount):
    coins = [500, 100, 50, 10]
    count = 0

    for coin in coins:
        count += amount // coin
        amount %= coin

    return count

• 큰 단위의 동전이 작은 단위 동전의 배수이므로 큰 동전부터 사용하는 선택이 최적해를 만듭니다.
• 하지만 동전이 [500, 400, 100]이고 800원을 만들어야 한다면 500원부터 선택하는 방법은 최적이 아닙니다.

 

그리디 선택: 500 + 100 + 100 + 100 = 4개
최적해: 400 + 400 = 2개

• 같은 형태의 문제라도 조건에 따라 그리디를 사용할 수 있는지가 달라집니다.

---

11. 회의실 배정 예제

한 회의실에서 겹치지 않게 최대한 많은 회의를 진행하려고 합니다.

가장 빨리 끝나는 회의부터 선택하면 남은 시간을 가장 많이 확보할 수 있습니다.

def max_meetings(meetings):
    meetings.sort(key = lambda x: (x[1], x[0]))

    count = 0
    end_time = 0

    for start, end in meetings:
        if (start >= end_time):
            count += 1
            end_time = end

    return count

• 종료 시간을 기준으로 오름차순 정렬하고, 종료 시간이 같다면 시작 시간을 기준으로 정렬합니다.
• 현재 회의가 이전에 선택한 회의가 끝난 뒤 시작한다면 선택합니다.
• 정렬에 O(N log N), 순회에 O(N)이 필요하므로 전체 시간복잡도는 O(N log N)입니다.

---

12. 그리디 문제 해결 순서

그리디 문제는 다음 순서로 접근할 수 있습니다.

1. 매 순간 무엇을 선택할지 기준을 정합니다.
2. 선택한 결과가 다음 선택에 어떤 영향을 주는지 확인합니다.
3. 현재의 최선 선택이 최종 결과에서도 손해가 아님을 설명합니다.
4. 정렬이나 우선순위 큐가 필요한지 확인합니다.
5. 반례를 만들어 선택 기준이 항상 성립하는지 검증합니다.

 

그리디에서는 코드를 작성하는 것보다 선택 기준이 올바른지 증명하는 과정이 더 중요할 수 있습니다.

---

13. 정렬과 그리디

그리디 문제는 특정 기준으로 데이터를 정렬한 뒤 순서대로 선택하는 형태가 자주 등장합니다.

weights = [4, 1, 2, 7, 3]
weights.sort()

 

다음과 같은 기준을 고려할 수 있습니다.

• 가장 작은 값부터 선택
• 가장 큰 값부터 선택
• 가장 빨리 끝나는 항목부터 선택
• 비용이 낮은 항목부터 선택
• 두 값의 차이가 큰 항목부터 선택

 

문제의 목표에 따라 올바른 정렬 기준이 달라집니다.

---

14. 그리디가 실패하는 경우

다음과 같은 상황에서는 단순한 그리디 선택이 최적해를 보장하지 않을 수 있습니다.

• 현재 선택이 이후의 선택 가능성을 크게 바꾸는 경우
• 여러 선택을 조합해야 최적해를 알 수 있는 경우
• 같은 상태에 도달하는 여러 방법의 결과를 비교해야 하는 경우

 

이런 문제는 DP, 완전탐색, 최단 경로 알고리즘 등이 더 적합할 수 있습니다.

예를 들어 각 선택의 결과를 저장하며 최댓값이나 최솟값을 구해야 한다면 DP를 고려할 수 있습니다.

---

15. 최단 경로와 그리디의 관계

다익스트라 알고리즘도 현재 거리가 가장 짧은 노드를 먼저 선택한다는 점에서 그리디한 방식이 사용됩니다.

 

간선의 비용이 음수가 없다는 조건에서, 선택된 최단 거리는 이후에 더 짧아지지 않습니다.

따라서 다익스트라는 다음 두 요소를 함께 사용한다고 볼 수 있습니다.

• 그리디: 현재 거리가 가장 짧은 노드를 선택
• 거리 갱신: 선택한 노드를 거쳐 가는 더 짧은 경로 저장

 

알고리즘의 동작뿐 아니라 어떤 조건 때문에 선택이 안전한지 이해하는 것이 중요합니다.

---

16. 자주 하는 실수/주의점

• 문제에 최솟값이나 최댓값이 나온다고 모두 그리디 문제는 아닙니다.
• 선택 기준을 정한 뒤 작은 반례를 만들어 확인해야 합니다.
• 정렬 기준이 여러 개라면 튜플 형태의 key를 사용할 수 있습니다.
• 다익스트라와 BFS는 간선 비용의 조건이 다릅니다.
• 다익스트라에서는 음수 간선을 사용할 수 없습니다.
• 연결되지 않은 노드의 처리 방법을 확인해야 합니다.
• 그리디 풀이에는 현재 선택이 최적해를 보장하는 이유가 필요합니다.

---

17. 종합 요약

• 최단 경로는 그래프에서 비용의 합이 가장 작은 경로를 탐색
• 모든 간선 비용이 같으면 BFS 사용 가능
• 음수가 없는 가중치 그래프에서는 다익스트라 사용
• 다익스트라는 최소 힙으로 가장 가까운 노드를 선택
• 그리디는 매 순간 현재 상황에서 가장 좋은 선택을 수행
• 그리디는 모든 문제에서 최적해를 보장하지 않음
• 정렬은 그리디 문제의 선택 순서를 만드는 데 자주 활용
• 선택 기준의 정당성과 반례를 반드시 확인