F-1: 고급 그래프 ① 최단 경로 — 걸음 수가 아니라 비용으로 길을 고른다

안녕하세요, 여러분의 알고리즘 길잡이 홍순구 튜터입니다. 지난 시간(E-5)까지 우리는 문제를 푸는 다섯 가지 사고법을 전부 손에 넣었어요. 재귀와 완전탐색, DFS와 BFS, 그리디와 분할정복, 그리고 동적 계획법까지. 그러면서 제가 마지막에 이렇게 예고했죠. "지금까지 쌓은 자료구조와 패러다임이 F에서 한데 모인다." 오늘이 그날입니다.

오늘 만날 다익스트라는 혼자 서 있는 알고리즘이 아니에요. C-2에서 배열로 직접 짜 본 힙이 우선순위 큐로 들어오고, C-3의 인접 리스트가 무대가 되고, E-2의 BFS가 골격을 빌려주고, E-3의 그리디가 "왜 이게 맞는가"를 증명해 줍니다. 넷이 한 자리에서 만나 하나의 알고리즘이 되는 셈이죠. 그래서 오늘은 새로 외울 게 많은 시간이 아니라, 이미 아는 것들이 맞물리는 시간입니다.

시작은 E-2에서 우리가 그어 둔 선 하나를 다시 꺼내는 데서 출발할게요. "간선의 걸음값이 모두 같으면 BFS가 곧 최단 경로다." 오늘은 그 걸음값이 제각각인 세계로 넘어갑니다. 도로마다 길이가 다르고, 노선마다 요금이 다르고, 구간마다 걸리는 시간이 다른 진짜 지도 같은 그래프요. 그러면 BFS가 어떻게 무너지는지, 무엇으로 갈아 끼워야 하는지를 오늘 내내 따라갑니다.

 오늘의 여정 — 걸음 수가 아니라 비용으로 길을 고른다

   최단 경로 문제       걸음값이 다르면 BFS가 깨진다
     │                 우선순위 큐로 갈아 끼우면 다익스트라
     │
   다익스트라 O(V²)     미확정 중 최소를 매번 훑어 고른다
     │
   다익스트라 힙        C-2의 힙으로 최소를 O(log V)에 꺼낸다
     │                 O(E log V) — 실전의 기본값
     ▼
   경로 복원            거리 말고 "어디를 거쳤나"를 되짚는다
     │
   벨만-포드            음수 간선이 끼면 그리디가 깨진다
     │                 이완 V-1회 + 음의 사이클 검출
     ▼
   플로이드-워셜        모든 쌍의 거리를 삼중 루프로 한꺼번에
     │
   셋 중 고르기         입력을 보고 알고리즘을 판별한다

💡 오늘 수업의 핵심 — "간선에 가중치가 생기면 걸음 수와 비용이 갈라진다 — BFS의 큐를 우선순위 큐로 갈아 끼운 다익스트라가 기본값이고, 음수 간선이면 벨만-포드, 모든 쌍이면 플로이드-워셜로 간다"

🎯 학습 목표

• 가중치 그래프에서 BFS가 왜 최단을 보장하지 못하는지 반례로 확인하고, 다익스트라의 그리디 선택이 왜 옳은지를 교환 논법으로 설명한다.
• 다익스트라를 선형 탐색 O(V²)과 힙 O(E log V) 두 방식으로 구현해 대조하고, 부모 배열로 실제 경로까지 복원한다.
• 음수 간선이면 벨만-포드, 모든 쌍이 필요하면 플로이드-워셜로 갈아타는 판단 기준을 입력 크기와 빅오로 세운다.

Step 1: "가장 짧은 길은 어떻게 고르나" (~20분)

E-2에서 우리가 BFS로 미로의 최단 거리를 구했던 걸 떠올려 보세요. 큐에 넣고 한 겹씩 넓혀 나가다가, 목적지에 처음 닿은 순간이 곧 최단 거리였습니다. 물결이 퍼지듯 가까운 곳부터 차례로 닿으니까요. 그때 제가 조건 하나를 분명히 달아 뒀어요. 이건 간선의 걸음값이 모두 1로 똑같을 때만 성립한다고요.

이제 그 조건을 치워 봅시다. 지도를 생각해 보세요. 서울에서 부산까지 가는 길이 여러 개인데, 어떤 길은 고속도로라 한 번에 이어지지만 400km고, 어떤 길은 국도를 세 번 갈아타지만 합쳐서 300km입니다. "몇 번 갈아탔나"와 "총 몇 km인가"는 전혀 다른 이야기죠. BFS는 앞의 것만 셀 수 있습니다.

 걸음 수와 비용이 정반대로 갈리는 그래프

    0 --------------(100)--------------> 1      간선 1개, 비용 100
    |                                    ^
    +--(1)--> 2 --(1)--> 3 --(1)---------+      간선 3개, 비용 3

BFS에게 0에서 1까지 가는 길을 물으면 뭐라고 답할까요? "한 걸음이면 닿습니다"라고 답합니다. 큐에서 0을 꺼내 이웃을 보는 순간 1이 바로 튀어나오니까요. 하지만 실제로 싼 길은 2와 3을 거치는 우회로예요. 1+1+1로 겨우 3이니까요. 걸음 수를 세는 자로는 비용을 잴 수 없습니다. 여기서 BFS가 깨집니다.

그러면 무엇을 바꿔야 할까요? 문제는 BFS가 큐에 들어온 순서대로 꺼낸다는 데 있습니다. 먼저 들어왔다고 해서 가까운 게 아니거든요. 그러니 꺼내는 기준을 "들어온 순서"가 아니라 "지금까지 알아낸 거리가 가장 짧은 것"으로 바꾸면 됩니다. 그런 자료구조, 우리 이미 갖고 있죠. C-2에서 배열로 직접 짜 본 힙, 곧 우선순위 큐입니다.

이게 다익스트라(Dijkstra)의 전부예요. BFS의 큐를 우선순위 큐로 갈아 끼우는 것. 골격은 그대로 두고 꺼내는 규칙만 바꾸는 겁니다.

 BFS와 다익스트라 — 골격은 같고 꺼내는 규칙만 다르다

   BFS          큐(deque)에서 꺼낸다      → 먼저 들어온 것부터
   다익스트라    힙(heapq)에서 꺼낸다      → 거리가 가장 짧은 것부터

   둘 다: 꺼낸다 → 이웃을 본다 → 갱신되면 넣는다 (반복)

그런데 잠깐, 여기서 한 번 의심하고 넘어가야 합니다. "지금 가장 가까워 보이는 것"을 꺼내서 그 거리를 확정해 버리는 건, 눈앞의 최선을 집는 그리디잖아요. E-3에서 우리는 그리디가 거스름돈 문제에서 보기 좋게 깨지는 걸 봤습니다. 그러면 다익스트라의 그리디는 왜 안 깨질까요?

교환 논법으로 따져 봅시다. 아직 확정 안 된 정점 중에서 거리가 가장 작은 정점 u를 꺼냈다고 해요. 만약 u에 더 짧게 닿는 다른 길이 있다면, 그 길은 아직 확정되지 않은 어떤 정점을 반드시 거쳐 가야 합니다. 그런데 그 정점의 거리는 이미 u의 거리보다 크거나 같아요. u가 미확정 중 최소였으니까요. 거기서 간선을 더 타고 걸어가 봐야 거리는 줄지 않습니다. 간선 가중치가 음수가 아닌 한 더할수록 커지거나 그대로일 뿐이니까요. 그러니 u보다 짧은 길은 존재할 수 없고, 꺼내는 순간이 곧 확정입니다.

 왜 "미확정 중 최소"를 꺼내면 확정인가

   u = 미확정 중 거리가 가장 작은 정점 (거리 d)

   u에 더 짧게 닿는 길이 있다고 치면
     그 길은 미확정 정점 x 를 반드시 거친다
     그런데 x 의 거리 ≥ d   (u가 미확정 중 최소였으므로)
     거기서 더 걸어가면 ≥ d + (0 이상 가중치) ≥ d

   → 모순. u 의 거리 d 는 더 줄어들 수 없다

이 논증이 통째로 기대고 있는 전제가 보이시나요? 마지막 줄의 "0 이상 가중치"입니다. 가중치가 0이면 등호가 되지만 "더 줄지는 않는다"는 결론은 그대로 성립하니, 정확한 전제는 양수가 아니라 음수가 아니다예요. 음수 간선이 하나라도 있으면 "더 걸어가면 줄지 않는다"가 무너지고, 확정했던 거리가 나중에 뒤집힐 수 있습니다. 그래서 음수 간선이 끼는 순간 다익스트라를 버려야 해요. 그럼 뭘 쓰냐고요? Step 5에서 만날 벨만-포드입니다. 오늘 그 순간까지 이 전제를 계속 염두에 두고 가세요.

💡 한 줄 정리

간선에 가중치가 생기면 걸음 수와 비용이 갈라져 BFS의 최단 보장이 깨진다. 다익스트라는 BFS의 큐를 우선순위 큐로 갈아 끼워 "지금까지 알아낸 거리가 가장 짧은 정점"부터 꺼내 확정하며, 이 그리디 선택이 옳다는 근거는 간선 가중치가 음수가 아니라는 전제 위에 서 있다.

Step 2: "거리 배열 하나로 시작한다" (~20분)

원리를 잡았으니 손으로 짜 볼 차례입니다. 그런데 첫 구현에서는 일부러 힙을 쓰지 않을게요. 힙 없이, 가장 단순하게 먼저 만들어 봅니다. 그래야 "힙이 정확히 무엇을 대신해 주는가"가 선명해지거든요.

다익스트라의 뼈대는 딱 두 줄로 요약됩니다.

 다익스트라의 뼈대 — 이 두 줄이 전부다

   ① 아직 확정 안 된 정점 중 거리가 가장 작은 것을 고른다 → 확정
   ② 그 정점의 이웃으로 가는 거리를 더 짧아지면 갱신한다 → 이완

   ①②를 정점 수만큼 반복하면 모든 최단 거리가 나온다

②에 나온 이완(relaxation)이라는 말을 짚고 갈게요. 팽팽하게 당겨져 있던 줄을 느슨하게 푼다는 뜻인데, 여기서는 "지금 알고 있는 거리보다 더 짧은 길을 찾았으면 그 값으로 줄인다"를 가리킵니다. 오늘 배울 세 알고리즘이 전부 이 이완을 반복하고, 무엇을 어떤 순서로 이완하느냐만 다릅니다. 오늘의 공통 언어예요.

이제 ①을 어떻게 구현하느냐가 성능을 가릅니다. 가장 단순한 방법은 아무 자료구조도 쓰지 않고 정점을 전부 훑어 최소를 찾는 거예요.

# algorithms/dijkstra.py
def dijkstra_matrix(graph, start):
    vertices = _vertices(graph)
    dist = {v: INF for v in vertices}
    dist[start] = 0
    visited = set()

    for _ in range(len(vertices)):
        # ① 미확정 정점 중 거리가 가장 작은 것을 선형 탐색으로 고른다 — 여기가 O(V)
        current = None
        smallest = INF
        for v in vertices:
            if v not in visited and dist[v] < smallest:
                smallest = dist[v]
                current = v
        if current is None:
            break                       # 남은 건 전부 못 닿는 정점 — 더 볼 게 없다
        visited.add(current)            # 꺼낸 순간 확정(그리디 선택)

        # ② 이웃으로 가는 거리를 더 짧게 만들 수 있으면 갱신한다(이완)
        for nxt, weight in graph.get(current, []):
            if dist[current] + weight < dist[nxt]:
                dist[nxt] = dist[current] + weight
    return dist

그래프는 C-3의 인접 리스트를 가중치까지 담도록 늘린 형태입니다. {정점: [(이웃, 가중치), ...]} 꼴이에요. E-2에서 쓰던 {정점: [이웃, ...]}에 무게가 하나씩 붙었다고 보시면 됩니다.

INF는 float('inf'), 곧 무한대입니다. 아직 닿지 못한 정점의 거리를 이 값으로 두는데, 이게 은근히 편해요. 어떤 실제 거리와 비교해도 무조건 지니까 "아직 모르는 곳"이 자연스럽게 걸러지고, inf + 가중치도 여전히 inf라 못 닿는 곳을 경유하는 길이 저절로 배제됩니다.

실제로 어떻게 도는지 거리표를 따라가 볼게요. 아래 그래프에서 0을 출발점으로 잡습니다.

 예제 그래프 (화살표 옆 숫자가 가중치)

    0 --(4)--> 1        0 --(1)--> 2
    1 --(1)--> 3        2 --(2)--> 1
    2 --(5)--> 3        3 --(3)--> 4
    5 : 들어오는 간선이 없어 0에서 못 닿는다

 거리표(dist)가 갱신되는 과정 — 확정된 정점은 [ ] 로 표시

  회차   확정    dist[0] dist[1] dist[2] dist[3] dist[4] dist[5]
  ----   ----    ------- ------- ------- ------- ------- -------
   시작   -         0      inf     inf     inf     inf     inf
    1    [0]        0       4       1      inf     inf     inf
    2    [2]        0       3       1       6      inf     inf
    3    [1]        0       3       1       4      inf     inf
    4    [3]        0       3       1       4       7      inf
    5    [4]        0       3       1       4       7      inf

2회차를 눈여겨보세요. 1번 정점의 거리가 4에서 3으로 줄어들었죠. 0에서 1로 곧장 가면 4인데, 2를 거쳐 돌아가면 1+2=3이라 더 싸거든요. Step 1에서 본 "우회로가 더 싼" 상황이 실제로 일어난 순간입니다. 만약 BFS였다면 0에서 한 걸음에 닿는 1을 4로 확정해 버리고 끝났을 거예요.

그리고 5번 정점은 끝까지 inf로 남습니다. 아무도 5를 가리키지 않아 도달할 방법이 없거든요. dijkstra_matrix(graph, 0)을 돌리면 {0: 0, 1: 3, 2: 1, 3: 4, 4: 7, 5: inf}가 나옵니다. 여기서 E-2의 BFS와 다른 점이 하나 있어요. BFS 거리 함수는 못 닿는 정점을 아예 결과에 안 넣었지만, 다익스트라는 키는 두되 값을 inf로 남깁니다. "못 닿는다"는 것도 정보니까요.

빅오를 따져 봅시다. 바깥 반복이 정점 수만큼 V번 돌고, 그 안에서 최소를 찾느라 다시 V개를 훑으니 시간 O(V²)입니다. 이완은 전체를 통틀어 간선 수 E번만 일어나는데, 보통 E ≤ V²라 O(V²)에 묻혀요. 공간은 거리표와 확정 집합으로 O(V)입니다.

"1초에 약 1억 연산" 잣대를 대 볼까요. V²이 1억이면 V는 약 10,000입니다. 정점이 1만 개를 넘어가면 이 방식으로는 시간 안에 못 들어와요. 그 벽을 다음 Step에서 힙으로 넘습니다.

💡 한 줄 정리

다익스트라는 "미확정 중 최소 거리 정점을 확정하고, 그 이웃을 이완한다"를 정점 수만큼 반복한다. 최소를 선형 탐색으로 고르면 한 번에 O(V)라 전체 시간 O(V²)·공간 O(V)이고, 1초 1억 연산 잣대로 정점 1만 개 언저리가 한계다.

Step 3: "가장 가까운 후보를 힙에서 꺼낸다" (~20분)

Step 2의 병목이 어디였는지 정확히 짚어 봅시다. "미확정 중 최소를 찾겠다고 매번 V개를 훑는" 그 안쪽 반복문이었어요. 알고리즘 전체가 O(V²)가 된 이유가 오직 그것 하나입니다.

그런데 "최소를 빠르게 꺼내는 그릇", 우리 C-2에서 이미 만들었잖아요. 힙 말입니다. 배열로 완전 이진트리를 표현하고, 삽입과 삭제를 O(log n)에 처리하던 그 자료구조요. 그때 제가 "이건 나중에 다익스트라에서 회수합니다"라고 예고했는데, 지금이 그 순간입니다.

def dijkstra_heap(graph, start):
    dist = {v: INF for v in _vertices(graph)}
    dist[start] = 0
    heap = [(0, start)]                 # (거리, 정점) — 힙이 거리 기준으로 정렬한다

    while heap:
        current_dist, node = heapq.heappop(heap)    # 가장 가까운 정점을 O(log V)에
        if current_dist > dist[node]:
            continue                    # 게으른 삭제: 이미 더 짧은 길을 찾은 철 지난 항목
        for nxt, weight in graph.get(node, []):
            new_dist = current_dist + weight
            if new_dist < dist[nxt]:    # 더 짧아질 때만 갱신하고 힙에 넣는다
                dist[nxt] = new_dist
                heapq.heappush(heap, (new_dist, nxt))
    return dist

E-2의 BFS 코드와 나란히 놓고 보면 골격이 얼마나 닮았는지 보일 거예요. deque가 heapq로, popleft()가 heappop()으로 바뀐 게 사실상 전부입니다. 꺼내는 규칙만 갈아 끼웠다는 Step 1의 말이 코드로 그대로 드러나죠.

튜플 (거리, 정점)을 힙에 넣는 게 요령입니다. 파이썬은 튜플을 앞 원소부터 비교하니, 첫 번째 자리에 거리를 두면 힙이 알아서 거리 기준으로 정렬해 줘요. C-2에서 최대 힙이 필요할 때 값에 음수를 붙였던 것과 같은 종류의 요령입니다.

여기서 하나 새로운 관용구가 등장하는데, if current_dist > dist[node]: continue 이 두 줄입니다. 왜 필요할까요?

 게으른 삭제(lazy deletion)가 필요한 이유

   1번 정점의 거리가 4 → 3 으로 줄었다고 하자

   힙 안:  (3, 1)  (4, 1)   ← 낡은 (4,1) 이 그대로 남아 있다
                            heapq 에는 특정 원소만 지우는 기능이 없다

   꺼낼 때 걸러낸다:
     (3, 1) 꺼냄 → dist[1] 이 3 → 유효, 처리한다
     (4, 1) 꺼냄 → dist[1] 이 3 → 4 > 3 이므로 철 지난 항목, 건너뛴다

거리가 갱신될 때마다 새로 넣기만 하고 낡은 항목은 힙 안에 그대로 둡니다. heapq에는 임의의 원소를 찾아 지우는 기능이 없거든요. 대신 꺼내는 순간에 "지금 기록된 거리보다 큰 값이면 이미 철 지난 것"으로 판단해 건너뜁니다. 지울 시점을 미룬다고 해서 게으른 삭제라고 불러요. 코딩테스트 다익스트라 코드에서 거의 항상 보게 될 두 줄이니 눈에 익혀 두세요.

이제 두 트랙을 나란히 놓고 비교해 봅시다.

재미있는 건 힙 버전이 항상 빠르지는 않다는 점이에요. 간선이 빽빽해서 E가 V²에 가까우면 O(E log V)는 O(V² log V)가 되어, 선형 탐색판의 O(V²)보다 log V만큼 오히려 손해입니다. 완전 그래프에 가까운 조밀한 입력이라면 단순한 쪽이 이기는 거죠.

다만 실전에서는 힙 버전을 기본값으로 잡으시면 됩니다. 코딩테스트에 나오는 그래프는 도로망이나 관계망처럼 거의 항상 성글거든요. 정점이 10만 개여도 간선은 20만 개 남짓인 식이에요. 이런 입력에서 O(V²)는 100억이라 손도 못 대지만, O(E log V)는 넉넉히 통과합니다.

🌟 실전 기본값: 가중치 그래프의 최단 경로는 heapq 다익스트라로 시작하세요. 정점이 수백 이하로 아주 작고 간선이 조밀한 예외적인 경우에만 선형 탐색판을 떠올리면 충분합니다.

두 함수가 정말 같은 답을 내는지는 코드베이스 test_dijkstra.py가 같은 그래프를 양쪽에 넣어 비교하는 방식으로 확인해 두었습니다. 원리 트랙과 실전 트랙이 어긋나지 않는다는 걸 기계로 보증해 둔 거예요.

💡 한 줄 정리

힙(C-2)을 우선순위 큐로 쓰면 "미확정 중 최소 꺼내기"가 O(V)에서 O(log V)로 줄어 전체가 O(E log V)가 된다. heapq에는 임의 삭제가 없어 낡은 항목을 그대로 두고 꺼낼 때 걸러 내는 게으른 삭제 관용구를 쓰며, 간선이 성근 실전 그래프에서는 이 힙 버전이 기본값이다.

Step 4: "어느 길로 갔는지 되짚기" (~20분)

지금까지 우리가 얻은 건 거리표뿐입니다. "0에서 4까지 7이 든다"는 알지만, "그래서 어느 길로 가야 하나요?"라는 질문에는 아직 답을 못 해요. 내비게이션이 "부산까지 400km입니다"라고만 하고 경로는 안 알려 주는 셈이죠.

그런데 이 문제, 우리 이미 한 번 풀어 봤습니다. E-4의 make_1 기억나시나요? 최소 연산 횟수를 구하면서 "이 값이 어디서 왔는지"를 함께 적어 뒀다가 거꾸로 되짚어 경로를 복원했죠. E-5의 LCS 문자열 복원도 같은 수법이었고요. 그때 제가 이렇게 못 박았습니다. "최적값을 구하는 알고리즘을 짰다면, 출처 배열 하나만 더 두면 경로도 나온다." 그 원칙이 그래프에서도 그대로 통합니다.

방법은 정말로 한 줄 추가예요. 어떤 정점의 거리를 갱신할 때, "누구를 거쳐서 짧아졌는지"를 함께 기록해 두면 됩니다.

def dijkstra_with_path(graph, start, end):
    dist = {v: INF for v in _vertices(graph)}
    dist[start] = 0
    previous = {start: None}            # 각 정점에 '어디서 왔는지'를 적어 둔다
    heap = [(0, start)]

    while heap:
        current_dist, node = heapq.heappop(heap)
        if current_dist > dist[node]:
            continue                    # 게으른 삭제
        if node == end:
            break                       # 목적지를 확정했으면 더 볼 필요가 없다
        for nxt, weight in graph.get(node, []):
            new_dist = current_dist + weight
            if new_dist < dist[nxt]:
                dist[nxt] = new_dist
                previous[nxt] = node    # 이 정점으로 오는 최단 길의 직전 정점
                heapq.heappush(heap, (new_dist, nxt))

    if dist.get(end, INF) == INF:
        return INF, []                  # 끝내 못 닿았다(그래프에 없는 정점도 여기로)

    path = []                           # end에서 previous를 거꾸로 타고 start까지
    node = end
    while node is not None:
        path.append(node)
        node = previous[node]
    path.reverse()                      # 거꾸로 모았으니 뒤집으면 start→end
    return dist[end], path

Step 3 코드에서 새로 붙은 건 previous 딕셔너리 하나와, 그걸 채우는 previous[nxt] = node 한 줄, 그리고 마지막에 거꾸로 타고 올라가는 반복문입니다. 알고리즘의 뼈대는 손도 대지 않았어요.

역추적이 어떻게 도는지 그림으로 보겠습니다. Step 2의 예제 그래프에서 0에서 4까지의 경로를 복원해 볼게요.

 previous 를 거꾸로 타고 올라가 경로를 복원한다

   기록된 previous:   4 ← 3      3 ← 1      1 ← 2      2 ← 0      0 ← None

   4 에서 시작해 거꾸로:
     4 → previous[4] = 3
     3 → previous[3] = 1
     1 → previous[1] = 2
     2 → previous[2] = 0
     0 → previous[0] = None   (여기서 멈춘다)

   모인 순서:  [4, 3, 1, 2, 0]
   뒤집으면:   [0, 2, 1, 3, 4]   ← 이게 최단 경로

dijkstra_with_path(graph, 0, 4)를 돌리면 (7, [0, 2, 1, 3, 4])가 나옵니다. 거리 7과 실제로 지나간 정점들이 함께 나오죠. 0에서 1로 곧장 가지 않고 2를 거쳐 도는 게 눈으로 확인됩니다.

닿을 수 없는 경우도 챙겨야 해요. dijkstra_with_path(graph, 0, 5)는 (inf, [])를 냅니다. 5번은 들어오는 간선이 없어 못 닿으니, 거리는 무한대이고 경로는 빈 리스트입니다. 아예 그래프에 없는 정점 번호를 넣어도 마찬가지로 (inf, [])가 나와요. "없는 정점"도 결국 "못 닿는 정점"이니까요.

한 가지 더, if node == end: break가 눈에 띄실 겁니다. 목적지를 확정한 순간 나머지는 볼 필요가 없어 일찍 빠져나오는 최적화예요. Step 1에서 증명했듯 힙에서 꺼내는 순간이 곧 확정이라, 그때 멈춰도 답이 틀리지 않습니다. 다만 이건 한 목적지만 물을 때의 요령이에요. 모든 정점까지의 거리가 필요하면 이 줄을 빼야 합니다.

시간·공간 복잡도는 Step 3과 같은 O(E log V)·O(V)입니다. previous 딕셔너리가 O(V) 더 붙지만 이미 O(V)라 변하지 않아요. 경로 정보를 공짜에 가깝게 얻는 셈이죠.

💡 한 줄 정리

거리만으로는 "얼마나 드나"만 알고 "어디를 거치나"는 모른다. 이완할 때마다 직전 정점을 previous에 기록해 두고 목적지에서 거꾸로 타고 올라간 뒤 뒤집으면 최단 경로가 복원되며, 이는 E-4·E-5에서 익힌 "값과 함께 출처를 남긴다"는 역추적 기법을 그래프로 옮긴 것이다. 복잡도는 경로 복원을 붙여도 그대로 O(E log V)다.

Step 5: "음수 간선이 끼면 그리디가 깨진다" (~20분)

Step 1에서 제가 조건 하나를 계속 머리에 두고 가자고 했죠. 다익스트라의 정당성은 "간선 가중치가 음수가 아니다"에 통째로 기대고 있다고요. 이제 그 전제를 깨 볼 시간입니다.

음수 간선이 대체 어디에 있냐고요? 생각보다 자연스럽게 등장합니다. 환전 수수료 대신 환차익이 나는 거래, 통행료를 내다가 보조금을 받는 구간, 게임에서 체력을 깎다가 회복 아이템을 얻는 길처럼 "가는데 오히려 이득이 되는" 이동이 있으면 음수 간선이에요.

이럴 때 다익스트라가 어떻게 틀리는지, Step 2의 dijkstra_matrix로 직접 따라가 봅시다.

 다익스트라가 조용히 틀리는 그래프 (간선 2→1 의 가중치가 -5)

    0 --(1)--> 1 --(1)--> 3
    0 --(2)--> 2 --(-5)--> 1

 진행:
   0 확정(0)     → 이완: dist[1]=1, dist[2]=2
   미확정 최소는 1 (거리 1) → 1 을 확정하고 dist[3] = 1+1 = 2
   그다음 2 확정(2) → 이완: 2 + (-5) = -3 이라 dist[1] 이 -3 으로 줄어든다

   그런데 1 은 이미 확정돼 다시 보지 않는다
   → dist[3] 이 -3+1 = -2 로 갱신될 기회를 영영 잃는다

 결과 dist[3] = 2          정답(벨만-포드) dist[3] = -2

핵심은 "확정"이라는 개념 자체가 무너진다는 데 있습니다. 1번 정점의 거리가 나중에 -3으로 줄었는데, 이미 확정해 visited에 넣어 버린 탓에 그 정점을 지나가는 3번의 거리를 다시 계산하지 않아요. 확정이 확정이 아니게 된 겁니다. 그런데도 프로그램은 오류 하나 없이 2를 내놓습니다. 조용히 틀리는 거죠.

⚠️ 직접 돌려 보면 헷갈릴 수 있는 지점: 같은 그래프를 Step 3의 dijkstra_heap에 넣으면 정답 -2가 나옵니다. 이 구현에는 visited가 없어서, 거리가 줄면 그 정점을 힙에 다시 넣고 한 번 더 처리하거든요. 그런데 이건 자랑거리가 아니라 보증이 사라진 상태예요. 재방문이 몇 번 일어날지 아무도 보장하지 못해 O(E log V)라는 시간 보증이 깨지고, 최악의 그래프에서는 폭발적으로 느려집니다. 무엇보다 음의 사이클이 있으면 거리가 끝없이 줄어들어 영원히 멈추지 않아요. "음수 간선이면 다익스트라를 쓰지 않는다"는 원칙은 그대로입니다.

그래서 벨만-포드(Bellman-Ford)는 확정이라는 개념을 아예 버립니다. 순서를 따지지 않고, 그냥 모든 간선을 반복해서 훑으며 줄일 수 있으면 줄여요. Step 2에서 배운 이완만 무식하게 반복하는 겁니다.

def bellman_ford(num_vertices, edges, start):
    dist = {v: INF for v in range(num_vertices)}
    dist[start] = 0

    for _ in range(num_vertices - 1):           # V-1회차
        updated = False
        for u, v, weight in edges:
            # 아직 못 닿은 정점(inf)에서는 출발할 수 없다
            if dist[u] != INF and dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight      # 이완: 더 짧은 길을 찾았다
                updated = True
        if not updated:
            break                               # 한 회차 동안 아무것도 안 줄면 이미 끝난 것

    # V-1회차로 끝났어야 하는데 또 줄어든다면 음의 사이클이다
    for u, v, weight in edges:
        if dist[u] != INF and dist[u] + weight < dist[v]:
            return None
    return dist

입력이 인접 리스트가 아니라 [(u, v, w), ...] 간선 목록인 게 눈에 띌 거예요. 이 알고리즘은 "어떤 정점의 이웃"을 찾을 일이 없고 매 회차 간선을 통째로 훑기만 해서, 간선을 죽 늘어놓은 형태가 더 자연스럽습니다. 알고리즘이 그래프 표현을 고르는 셈이죠.

여기서 꼭 짚어야 할 게 왜 하필 V-1회인가입니다.

 왜 V-1 회 이완하면 충분한가

   사이클 없는 최단 경로가 지나는 정점은 최대 V 개
     → 그 경로가 쓰는 간선은 최대 V-1 개

   간선 전체를 훑는 한 회차마다
     최단 경로의 간선이 최소 하나씩은 제자리를 찾는다

   따라서 V-1 회차면 어떤 최단 경로든 완성된다

최단 경로에 사이클이 낄 이유가 없다는 게 출발점이에요. 같은 정점을 두 번 지나는 건 가중치가 음수가 아닌 한 손해니까요. 그러면 경로가 쓰는 간선은 최대 V-1개이고, 한 회차마다 최소 한 간선씩 확정되니 V-1회면 충분합니다.

그런데 여기서 음의 사이클이라는 골치 아픈 놈이 등장합니다. 사이클을 한 바퀴 돌았는데 가중치 합이 음수라면 어떻게 될까요?

 음의 사이클 — 돌수록 거리가 줄어든다

    1 --(-1)--> 2 --(-1)--> 3 --(-1)--> 1     한 바퀴 합계 = -3

    한 바퀴: -3      두 바퀴: -6      세 바퀴: -9  ...

    무한히 돌면 거리가 무한히 작아진다
    → 이 그래프에는 '최단' 이라는 답이 존재하지 않는다

이런 그래프에는 최단 경로가 아예 존재하지 않습니다. 계속 돌기만 하면 얼마든지 줄일 수 있으니까요. 그래서 벨만-포드는 V-1회를 다 돌고 나서 한 번 더 훑어봅니다. 이미 끝났어야 하는데 또 줄어든다면, 그건 음의 사이클이 있다는 신호예요. 이때 None을 돌려줍니다.

음의 사이클 검출은 덤이 아니라 벨만-포드의 중요한 쓸모예요. 코딩테스트에서 "시간을 거슬러 출발점으로 돌아올 수 있는가" 같은 문제가 나오면, 그건 사실 "음의 사이클이 있는가"를 묻는 겁니다.

실제로 돌려 보겠습니다. 간선이 [(0,1,4), (0,2,5), (1,2,-3), (1,3,7), (2,3,4), (3,4,2)]인 그래프에서 bellman_ford(5, edges, 0)은 {0: 0, 1: 4, 2: 1, 3: 5, 4: 7}을 냅니다. 2번 정점을 보세요. 0에서 곧장 가면 5인데, 1을 거쳐 4+(-3)=1로 가는 게 더 쌉니다. 음수 간선이 실제로 답을 바꾼 거죠. 반면 [(0,1,1), (1,2,-1), (2,3,-1), (3,1,-1)]처럼 음의 사이클이 있는 그래프에 넣으면 None이 나옵니다.

빅오는 정직하게 비쌉니다. V-1회차마다 간선 E개를 전부 훑으니 시간 O(V·E), 거리표만 들고 있어 공간 O(V)입니다. 1초 1억 잣대로 V·E가 1억 이하, 정점 수천에 간선 수만 정도까지가 현실적인 선이에요. 다익스트라의 O(E log V)보다 한참 느립니다.

⚠️ 그래서 순서가 이렇습니다: 음수 간선이 없으면 무조건 다익스트라입니다. 벨만-포드는 "음수 간선이 있어서 어쩔 수 없을 때" 또는 "음의 사이클을 찾아야 할 때"만 꺼내세요. 느린 알고리즘을 습관처럼 쓰면 시간 초과를 만납니다.

💡 한 줄 정리

음수 간선이 있으면 "한 번 꺼낸 정점은 확정"이라는 다익스트라의 전제가 무너진다. 벨만-포드는 확정을 포기하고 모든 간선을 V-1회 이완하며, 한 번 더 훑어도 줄어들면 음의 사이클로 판정해 None을 낸다. 시간 O(V·E)·공간 O(V)로 느린 대신 음수를 정면으로 다룬다.

Step 6: "모든 쌍의 거리를 한꺼번에" (~20분)

지금까지의 질문은 늘 "한 출발점에서 각 정점까지 얼마인가"였습니다. 그런데 문제가 이렇게 나온다면 어떨까요? "도시 100개가 있는데, 모든 도시 쌍 사이의 최단 거리를 전부 구하라."

다익스트라를 100번 돌리면 되긴 합니다. 실제로 그것도 정답이에요. 그런데 정점이 적을 때는 훨씬 짧은 코드로 끝내는 방법이 있습니다. 플로이드-워셜(Floyd-Warshall)입니다.

이 알고리즘이 던지는 질문은 놀랄 만큼 단순해요. 딱 하나입니다.

 플로이드-워셜의 유일한 질문

   "i 에서 j 로 갈 때, k 를 경유하면 더 짧아지나?"

     dist[i][j] = min( dist[i][j] , dist[i][k] + dist[k][j] )
                     (직행)        (k 를 거쳐 가기)

   이 질문을 모든 k, 모든 i, 모든 j 에 대해 던지면 끝

경유지를 하나씩 허락해 가며 거리를 줄여 나가는 겁니다. 그런데 이 구조, 어딘가 익숙하지 않나요? "k번째 정점까지만 경유지로 허용했을 때의 최단 거리"를 k를 하나씩 늘려 가며 채우는 것. E-4와 E-5에서 지겹도록 한 표 채우기, 곧 동적 계획법입니다. 상태가 "출발지 × 도착지" 두 축이라 2차원 표가 되고, 경유지 k가 그 표를 갱신하는 단계 역할을 해요.

def floyd_warshall(matrix):
    n = len(matrix)
    dist = [row[:] for row in matrix]           # 입력 비파괴 — 복사본에서 작업

    for k in range(n):                          # 경유지 k가 반드시 가장 바깥
        for i in range(n):
            if dist[i][k] == INF:
                continue                        # i에서 k에 못 닿으면 경유 자체가 불가
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

입력이 이번엔 인접 행렬입니다. matrix[i][j]가 i에서 j로 가는 가중치이고, 간선이 없으면 INF, 자기 자신은 0이에요. C-3에서 "정점이 적고 조밀하면 인접 행렬"이라고 배운 그 조건이 여기 딱 맞아떨어집니다. 모든 쌍의 거리를 담아야 하니 어차피 V×V 표가 필요하거든요.

이 알고리즘의 단골 실수를 지금 못 박고 갈게요. 삼중 루프의 순서, 특히 k가 반드시 가장 바깥이어야 한다는 겁니다.

 k 가 가장 바깥이어야 하는 이유

   k 를 바깥에 두면
     k=0 다 돌면 → "0 번만 경유지로 쓸 때" 의 모든 쌍 최단 거리 완성
     k=1 다 돌면 → "0,1 을 경유지로 쓸 때" 의 모든 쌍 최단 거리 완성
     k=2 다 돌면 → "0,1,2 를 경유지로 쓸 때" ...
     한 단계씩 답이 완성되며 쌓인다

   i 나 j 를 바깥에 두면
     dist[i][k] 나 dist[k][j] 가 아직 안 채워진 상태에서 참조된다
     → 틀린 답이 나온다

E-5의 구간 DP에서 "짧은 구간부터 채워야 긴 구간이 참조할 값이 준비된다"고 했던 것과 정확히 같은 원리예요. 작은 부분 문제가 먼저 완성돼 있어야 큰 문제가 그걸 딛고 설 수 있습니다. 여기서는 "경유지를 몇 개까지 허락했나"가 그 단계 역할을 하고요. 루프 순서를 i, j, k로 잘못 쓰면 조용히 틀린 답이 나오니, 손가락에 k가 먼저라고 새겨 두세요.

돌려 보겠습니다. 0에서 1로 4, 0에서 3으로 5, 1에서 2로 1, 2에서 3으로 3인 그래프를 인접 행렬로 넣으면 결과는 이렇습니다.

 플로이드-워셜 결과 (행 = 출발, 열 = 도착)

           →0     →1     →2     →3
    0→      0      4      5      5
    1→    inf      0      1      4
    2→    inf    inf      0      3
    3→    inf    inf    inf      0

0에서 2로 가는 직행 간선은 없는데 결과가 5로 채워졌죠. 1을 경유해서 4+1=5로 닿는 길을 찾아낸 겁니다. 0에서 3은 직행 5와 경유 5+3=8 중 직행이 이겨 5로 남았고요. 방향 그래프라 역방향은 전부 inf입니다.

빅오는 코드 모양 그대로예요. 삼중 루프니 시간 O(V³), 표 하나라 공간 O(V²)입니다. 1초 1억 잣대로 V³이 1억이면 V는 약 460인데, 파이썬은 반복문 상수가 커서 실전에서는 V 200~300 언저리가 현실적인 선입니다.

다익스트라를 V번 돌리는 것과 비교해 볼까요. 그쪽은 O(V·E log V)입니다. 간선이 성글면(E ≈ V) 이게 훨씬 빠르지만, 조밀하면(E ≈ V²) O(V³ log V)라 오히려 플로이드-워셜이 이겨요. 그리고 무엇보다 코드가 세 줄이라 실수할 여지가 적습니다. 정점이 작을 때 플로이드-워셜을 고르는 진짜 이유는 속도보다 간결함인 경우가 많아요.

💡 한 줄 정리

플로이드-워셜은 "i에서 j로 갈 때 k를 경유하면 짧아지나"를 모든 조합에 던져 모든 쌍의 최단 거리를 구하는 2차원 DP다. 경유지 k를 반드시 가장 바깥 루프에 둬야 단계별로 답이 완성되며, 시간 O(V³)·공간 O(V²)이라 정점 수백 이하일 때 쓴다.

   모든 i 에 대해  dist[i][i] < 0  이면  →  음의 사이클 존재

Step 7: "셋 중 무엇을 고르나" (~15분)

오늘 세 알고리즘을 만났습니다. 코딩테스트에서 진짜 시험대에 오르는 건 각각을 구현하는 능력이 아니라, 문제를 읽고 어느 것을 꺼낼지 3초 안에 정하는 능력이에요. 마지막 Step에서 그 판단 기준을 정리하겠습니다.

먼저 세 알고리즘을 한 표에 놓고 봅시다.

이 표를 외우려 하지 마시고, 아래 판단 순서를 몸에 붙이세요. 위에서부터 차례로 물으면 됩니다.

 최단 경로 알고리즘 고르는 순서

   ① 간선 가중치가 전부 같은가?
        예   → BFS (E-2). 다익스트라는 로그만큼 손해
        아니오 ↓

   ② 모든 쌍의 거리가 필요한가?
        예   → 정점이 작으면(수백 이하) 플로이드-워셜
                정점이 크고 간선이 성글면 다익스트라를 V 번
        아니오 ↓

   ③ 음수 간선이 있는가?
        예   → 벨만-포드 (음의 사이클도 여기서 검출)
        아니오 ↓

   ④ 그 외 전부 → 다익스트라 + heapq  (실전 기본값)

문제 지문에서 실마리를 읽어 내는 감각도 함께 챙겨 가시죠. 출제자는 보통 이런 말로 알고리즘을 알려 줍니다.

마지막 줄이 흥미롭죠. 실전 문제는 오늘 배운 알고리즘을 그대로 쓰기보다 살짝 비틀어 냅니다. "반드시 경유지 X를 거쳐 A에서 B로 가는 최단 거리"라면, A에서 출발하는 다익스트라 한 번과 X에서 출발하는 다익스트라 한 번을 돌려 dist_A[X] + dist_X[B]로 합치면 되고요. "왕복 최단 거리"라면 간선 방향을 전부 뒤집은 그래프를 하나 더 만들어 다익스트라를 돌립니다.

그러니 오늘 배운 다섯 함수를 부품으로 보세요. 문제가 요구하는 조립법이 매번 조금씩 다를 뿐, 부품 자체는 오늘 만든 것 그대로입니다.

마지막으로 입력 크기를 보고 판단하는 A-1의 습관을 다시 한번 되새기고 갈게요. 정점 10만 개에 간선 30만 개인 문제에 플로이드-워셜을 꺼내면 V³이 10의 15승이라 손도 못 댑니다. 반대로 정점 100개에 모든 쌍을 물었는데 다익스트라를 100번 짜면 코드만 길어지죠. 문제를 읽고 가장 먼저 볼 것은 언제나 입력 크기의 범위입니다.

💡 한 줄 정리

최단 경로 문제는 "가중치가 다 같은가 → 모든 쌍인가 → 음수가 있는가"를 차례로 물어 알고리즘을 고른다. 기본값은 다익스트라와 heapq이고, 모든 쌍에 정점이 작으면 플로이드-워셜, 음수 간선이나 음의 사이클이면 벨만-포드다. 실전 문제는 이 부품들을 두 번 돌리거나 그래프를 뒤집어 조립하는 형태로 나온다.

마무리

오프닝에서 오늘은 새로 외우는 시간이 아니라 이미 아는 것들이 맞물리는 시간이라고 했죠. 실제로 그랬는지 되짚어 볼까요. 힙은 최소를 꺼내는 그릇으로, 인접 리스트는 이웃을 훑는 통로로, BFS는 꺼내고 이완하는 골격으로, 교환 논법은 "왜 확정해도 되는가"의 증명으로, DP는 플로이드-워셜의 정체로 각각 제 몫을 했습니다. 새로 외운 것보다 다시 만난 것이 더 많은 하루였어요.

오늘 배운 핵심 세 가지

💡 하나 — 가중치가 생기면 걸음 수와 비용이 갈라진다. BFS가 최단을 보장하던 건 간선 값이 모두 같을 때뿐이었어요. 값이 제각각이면 간선 하나짜리 직행보다 간선 셋짜리 우회로가 쌀 수 있습니다. 그래서 큐를 우선순위 큐로 갈아 끼워 "먼저 들어온 것"이 아니라 "가장 가까운 것"을 꺼내는 다익스트라가 필요했죠. 골격은 BFS 그대로, 꺼내는 규칙만 바뀌었습니다.

💡 둘 — 그리디의 정당성은 전제 위에 서 있다. 미확정 중 최소를 꺼내면 곧 확정이라는 다익스트라의 근거는, 간선 가중치가 음수가 아니라는 전제에 통째로 기대고 있었어요. 음수 간선이 하나만 껴도 확정이 뒤집혀 알고리즘이 틀립니다. E-3에서 거스름돈 반례로 배운 "그리디는 정당성을 따져야 쓴다"가 그래프에서 다시 확인된 셈이에요. 전제가 깨지면 확정을 포기하고 이완만 반복하는 벨만-포드로 갑니다.

💡 셋 — 알고리즘은 외우는 게 아니라 고르는 것이다. 다익스트라·벨만-포드·플로이드-워셜은 우열이 아니라 용도가 다릅니다. 가중치가 같으면 BFS, 모든 쌍에 정점이 작으면 플로이드-워셜, 음수가 끼면 벨만-포드, 나머지는 다익스트라. 이 판단을 문제의 입력 크기와 조건에서 읽어 내는 게 A-1부터 깔아 온 빅오 감각의 최종 형태입니다.

다음 시간 예고

다음 시간(F-2)에는 고급 그래프의 나머지 절반, 집합과 순서를 다룹니다. 오늘 우리가 그래프에 던진 질문은 줄곧 "얼마나 먼가"였어요. 다음 시간의 질문은 달라집니다.

"이 둘이 같은 무리에 속하나?" — 친구의 친구의 친구까지 따라가지 않고도 한 번에 판별하는 유니온 파인드를 만납니다. 경로 압축이라는 기법 하나로 거의 O(1)에 가까워지는, 놀랍도록 짧고 강력한 자료구조예요.

"어떤 순서로 처리해야 하나?" — 선수 과목이 있는 수강 계획, 의존성이 얽힌 빌드 순서를 줄 세우는 위상 정렬입니다. C-3 과제에서 세어 본 진입 차수가 여기서 열쇠로 쓰이고, E-2의 BFS가 그대로 골격이 돼요.

"최소 비용으로 전부 잇는 방법은?" — 모든 정점을 가장 싸게 연결하는 최소 신장 트리(MST)를 크루스칼과 프림 두 갈래로 짭니다. 크루스칼은 유니온 파인드를, 프림은 오늘 쓴 힙을 그대로 가져다 써요.

그리고 오늘 제가 답을 미뤄 둔 질문 하나 기억하시죠. 사이클 없는 그래프의 최장 경로는 위상 정렬로 풀린다고 했던 것. 다음 시간에 회수하겠습니다.

과제

[기초] 신호가 모든 컴퓨터에 닿는 시간

네트워크에 컴퓨터 n대가 있고(번호 0부터 n-1), 단방향 연결이 [(출발, 도착, 지연시간), ...] 목록으로 주어집니다. start번 컴퓨터에서 신호를 보낼 때, 모든 컴퓨터가 신호를 받기까지 걸리는 시간을 반환하는 함수 network_delay(n, connections, start)를 작성하세요. 한 대라도 신호를 받을 수 없으면 -1을 반환합니다.

신호는 여러 갈래로 동시에 퍼져 나가므로, 각 컴퓨터는 자기에게 닿는 가장 빠른 경로의 시간에 신호를 받습니다. 그러니 전체가 다 받는 시간은 "가장 늦게 받는 컴퓨터의 시간"이 되겠죠. 간선 목록을 인접 리스트로 바꾸는 것부터 시작하면 됩니다. 시간·공간 복잡도를 빅오로 함께 적으세요.

[응용] 반드시 거쳐야 하는 곳이 있다면

가중치 방향 그래프와 출발점 start, 도착점 end, 그리고 반드시 거쳐야 하는 경유지 via가 주어집니다. start에서 출발해 via를 반드시 지나 end에 도착하는 최단 거리를 반환하는 함수 shortest_via(graph, start, via, end)를 작성하세요. 그런 경로가 없으면 float('inf')를 반환합니다.

핵심은 오늘 만든 함수를 부품으로 조립하는 데 있어요. 경유지를 반드시 지나야 한다면 그 경로는 두 토막으로 쪼개집니다. 어디를 어떻게 자를지, 그리고 각 토막을 무엇으로 구할지 생각해 보세요. 다익스트라를 몇 번 돌려야 하는지도 함께 답하시고, 전체 시간 복잡도를 빅오로 적으세요.

[심화] 갔다가 돌아오기

마을 n개가 단방향 도로로 이어져 있습니다. 모든 마을 사람들이 party번 마을의 잔치에 갔다가 자기 마을로 돌아옵니다. 각자 갈 때도 올 때도 최단 경로를 택할 때, 가장 오래 걸리는 사람의 왕복 시간을 반환하는 함수 longest_round_trip(n, roads, party)를 작성하세요.

도로가 단방향이라 갈 때와 올 때의 거리가 다르다는 게 함정입니다. party에서 각 마을로 가는 거리는 다익스트라 한 번이면 나오는데, 각 마을에서 party로 오는 거리는 어떻게 구할까요? 마을마다 다익스트라를 돌리면 n번이라 느립니다. 간선의 방향을 전부 뒤집은 그래프를 하나 만들어 보세요. 뒤집은 그래프에서 party를 출발점으로 삼으면 무엇이 나오는지 생각해 보시면 길이 열립니다. 다익스트라를 총 몇 번 돌리는지, 시간 복잡도가 얼마인지 함께 적으세요.

생각해볼 주제

1. 음수 간선 하나가 왜 알고리즘 전체를 무너뜨리나

다익스트라에 음수 간선이 있는 그래프를 넣으면, 프로그램은 오류 없이 멀쩡히 돌고 그럴듯한 숫자를 냅니다. 다만 그 숫자가 틀렸을 뿐이죠. 조용히 틀리는 이 성질이 실무에서는 특히 위험합니다. 다익스트라의 어떤 단계가 정확히 무엇을 가정하고 있길래 음수 간선 하나에 무너지는지, Step 1의 교환 논법으로 되짚어 설명해 보세요. 그리고 이런 "조용히 틀리는" 문제를 코딩테스트에서 미리 막으려면 무엇을 확인해야 할지도 함께 생각해 보시죠.

2. 더 빠른 알고리즘이 항상 더 나은 선택인가

O(E log V)인 힙 다익스트라는 O(V²)인 선형 탐색판보다 복잡도가 낮습니다. 그런데 간선이 빽빽한 그래프에서는 오히려 느려지고, 코드도 더 깁니다. 플로이드-워셜과 "다익스트라 V번"의 관계도 비슷하고요. 복잡도 표기의 대소 관계와 실제 성능이 갈리는 이유가 무엇인지, 그리고 알고리즘을 고를 때 빅오 말고 무엇을 함께 봐야 하는지 정리해 보세요.

3. 최단 경로 문제인지 어떻게 알아채나

오늘 다룬 알고리즘들은 지문에 "그래프"나 "최단 경로"라는 말이 없어도 등장합니다. 환전 경로, 작업 스케줄, 게임의 상태 전이처럼 겉보기엔 그래프와 무관해 보이는 문제가 실은 최단 경로 문제인 경우가 많아요. 어떤 문제를 그래프로 모델링할 수 있다고 판단하려면 무엇이 보여야 할까요? 정점과 간선에 각각 무엇을 대응시킬지를 정하는 기준을 세워 보시고, 오늘 배운 것 중 무엇을 쓸지까지 이어서 생각해 보세요.