F-2: 고급 그래프 ② 집합과 순서 — 같은 무리인가, 어떤 순서인가, 얼마에 다 잇는가

안녕하세요, 여러분의 알고리즘 길잡이 홍순구 튜터입니다. 지난 시간(F-1)에 우리가 그래프에 던진 질문은 처음부터 끝까지 하나였어요. "얼마나 먼가." 다익스트라로 최단 비용을 재고, previous로 지나온 길을 되짚고, 음수 간선이 끼면 벨만-포드로 갈아타고, 모든 쌍이 필요하면 플로이드-워셜로 표를 채웠죠. 거리를 재는 자는 이제 충분히 갖췄습니다.

오늘은 그 자를 내려놓고 그래프를 다른 눈으로 봅니다. 거리를 묻지 않는 질문 세 가지가 오늘의 전부예요. "이 둘이 같은 무리에 속하나", "어떤 순서로 처리해야 하나", "전부 잇는 가장 싼 방법은 얼마인가". 셋 다 간선의 길이를 재는 문제가 아니라 그래프를 집합과 순서로 다시 읽는 문제입니다.

그리고 지난 시간에 제가 갚기로 한 빚이 하나 있습니다. 어떤 분이 "다익스트라로 최장 경로를 구하면 안 되냐"고 물으셨고, 저는 일반 그래프에서는 NP-난해라 안 되지만 사이클 없는 방향 그래프(DAG)라면 풀린다고, 그때 필요한 "적절한 순서"를 만들어 주는 게 위상 정렬이라고 답하며 다음 시간으로 미뤘어요. 오늘 중반에 그 약속을 정확히 갚습니다.

 오늘의 여정 — 집합과 순서로 그래프를 다시 본다

   유니온 파인드        "이 둘이 같은 무리인가?"
     │                  집합마다 대표 한 명을 정해 둔다
     │
   경로 압축            한 번 훑은 길은 다음부터 한 걸음
     │
   union by rank        막대 트리가 생기는 것 자체를 막는다
     │                  사실상 O(α(n)) — 상수나 다름없다
     ▼
   위상 정렬            "어떤 순서로 처리해야 하나?"
     │                  진입 차수 0부터 줄을 세운다
     │
   DAG 최장 경로        지난 시간 미뤄 둔 약속을 갚는다
     ▼
   최소 신장 트리       "전부 잇는 가장 싼 방법은?"
     │                  크루스칼은 유니온 파인드로
     │                  프림은 힙으로

💡 오늘 수업의 핵심 — "그래프에 던질 질문은 거리만이 아니다 — 같은 무리인지는 유니온 파인드가, 처리 순서는 위상 정렬이, 전부 잇는 최소 비용은 최소 신장 트리가 답한다"

🎯 학습 목표

• 분리 집합을 직접 구현하고, 경로 압축과 union by rank가 각각 무엇을 막아 주는지 트리 높이와 걸음 수로 확인해 사실상 상수 시간까지 끌어내린다.
• 위상 정렬을 진입 차수 기반(BFS)과 DFS 기반 두 방식으로 짜고, 사이클 검출과 DAG 최장 경로까지 확장한다.
• 최소 신장 트리를 컷 성질로 이해한 뒤 크루스칼과 프림 두 갈래로 구현하고, 간선 밀도에 따라 어느 쪽을 고를지 빅오로 판단한다.

Step 1: "여러 그룹을 하나로 합치기" (~20분)

E-2에서 "이 두 정점이 이어져 있나"를 묻는 문제는 이미 풀어 봤죠. DFS나 BFS로 한 번 훑으면 O(V+E)에 연결 요소가 전부 나오니 그걸로 충분해 보입니다. 그런데 문제가 이렇게 물어오면 사정이 달라져요.

"친구 관계가 하나씩 새로 맺어지는데, 그때마다 두 사람이 같은 무리인지 답하라."

 친구 신청 (0,1)  →  0과 2는 같은 무리?  →  친구 신청 (1,2)  →  0과 2는?
                            아니오                                    예

간선이 하나 늘 때마다 그래프를 처음부터 다시 훑는다면 질의가 q개일 때 O(q(V+E))입니다. 정점 10만·간선 20만짜리 그래프에 질의가 10만 번 들어오면 300억 번 연산이에요. 손도 못 댑니다. 게다가 억울하죠. 방금 힘들게 알아낸 무리 정보를 버리고 매번 처음부터 다시 세고 있으니까요.

필요한 건 무리를 계속 들고 있으면서 합치고 묻는 자료구조입니다. 그게 오늘의 첫 주인공, 분리 집합(Disjoint Set) 이에요. 겹치지 않는 여러 집합으로 원소를 나눠 갖는 구조인데, 지원하는 연산이 딱 둘이라 그 이름을 따 유니온 파인드(Union-Find) 라고도 부릅니다.

• find(x) : x가 속한 집합의 대표를 알려준다
• union(a, b) : a의 집합과 b의 집합을 하나로 합친다

대표 한 명만 기억한다

발상이 정말 단순해요. 집합마다 대표 한 명을 정해 둔다는 겁니다.

같은 집합인지 묻는 건 두 원소의 대표가 같은지 보면 끝나고, 합치는 건 한쪽 대표를 다른 쪽 대표 밑에 매달면 끝납니다. 원소를 통째로 옮기는 게 아니라 대표 하나만 바꾸니 합치기가 쌉니다. 그리고 대표를 부모 포인터로 이어 두면, 집합 하나가 자연스럽게 트리 하나가 돼요. C-1에서 배운 트리가 여기서 이렇게 쓰입니다.

회사 조직도를 떠올리면 편해요. "우리 같은 팀이야?"를 확인하려면 각자 위로 올라가 팀장을 찾아보면 됩니다. 팀장이 같으면 같은 팀이죠. 두 팀을 합칠 때도 팀원 전원을 재배치할 필요 없이 한쪽 팀장이 다른 쪽 팀장 밑으로 들어가면 그만이고요.

코드로 옮기면 이렇습니다. 최적화를 하나도 얹지 않은 원형부터 보겠습니다.

# algorithms/union_find.py
class NaiveUnionFind:
    """최적화를 하나도 안 얹은 원형. find 최악 O(n)·union 최악 O(n)·공간 O(n)."""

    def __init__(self, n):
        self.parent = list(range(n))    # 처음엔 저마다 자기 자신이 대표 = 집합 n개
        self.count = n                  # 현재 집합 개수(연결 요소 개수)
        self.steps = 0                  # 학습용 — find가 밟은 부모 포인터 수 누적

    def find(self, x):
        """x가 속한 집합의 대표를 찾는다. 최악 O(n)(트리 높이만큼)."""
        while self.parent[x] != x:      # 자기 자신이 부모인 원소가 대표다
            x = self.parent[x]
            self.steps += 1
        return x

    def union(self, a, b):
        """a의 집합과 b의 집합을 합친다. 이미 같은 집합이면 False. 최악 O(n)."""
        root_a, root_b = self.find(a), self.find(b)
        if root_a == root_b:
            return False                # 이미 한 집합 — 합칠 게 없다
        self.parent[root_a] = root_b    # 높이를 안 보고 그냥 매단다 = 막대 트리의 씨앗
        self.count -= 1
        return True

    def connected(self, a, b):
        """두 원소가 같은 집합인가. find 두 번이므로 find와 같은 복잡도."""
        return self.find(a) == self.find(b)

__init__의 list(range(n))이 이 자료구조의 출발점이에요. parent[i] = i, 곧 모두가 자기 자신의 대표입니다. 아직 아무도 합쳐지지 않았으니 집합이 n개인 상태죠.

find의 규칙도 딱 한 줄입니다. "자기 자신이 부모인 원소가 대표" 예요. 그러니 부모를 계속 따라 올라가다가 자기 자신을 가리키는 원소를 만나면 거기가 루트, 곧 대표입니다. 재귀 대신 while 반복문으로 올라가는 게 눈에 띄실 텐데, 이건 나중에 다시 짚을게요.

steps는 실전 풀이에는 필요 없는 학습용 계측기입니다. find가 부모 포인터를 몇 번 밟았는지 누적해서, 최적화 전후를 "빨라진 것 같다"가 아니라 숫자로 비교하려고 달아 뒀어요. Step 2에서 이 숫자가 주인공이 됩니다.

union이 bool을 돌려주는 이유

union을 다시 보세요. 두 대표가 이미 같으면 아무것도 안 하고 False를 돌려줍니다. 그냥 "합칠 게 없었어요" 하는 안내문 같지만, 이 반환값이 오늘 두 번이나 열쇠로 쓰입니다.

False는 "이 둘은 원래 이어져 있었다" 는 뜻이거든요. 무방향 그래프에서 간선 하나를 집어 양 끝을 union 해 봤는데 False가 나왔다면, 그 간선은 새로 뭘 잇는 게 아니라 이미 있던 길에 고리를 하나 더한 겁니다. 곧 사이클이에요. 이 신호 하나로 사이클 검사가 끝나고, 그게 오늘 후반부 크루스칼의 심장이 됩니다. 지금은 "False는 그냥 실패가 아니라 정보다" 정도만 새겨 두세요.

실제로 돌려 보기

원소 다섯 개로 무리를 지어 보겠습니다.

uf = UnionFind(5)
uf.count            → 5
uf.union(0, 1)      → True
uf.union(1, 2)      → True
uf.connected(0, 2)  → True     # 직접 합친 적 없어도 같은 무리
uf.connected(0, 3)  → False
uf.union(0, 2)      → False    # 이미 한 집합
uf.count            → 3        # {0,1,2} {3} {4}

여기 쓴 UnionFind는 오늘 Step 3에서 완성할 실전 버전인데, 겉으로 나오는 답은 네 버전 모두 같습니다. 달라지는 건 안쪽 트리가 어떻게 생겼느냐뿐이에요.

부모 포인터가 어떻게 이어지는지 따라가 봅시다.

 처음엔 저마다 자기 자신이 대표 — 집합이 다섯 개

   parent : [0, 1, 2, 3, 4]
   0       1       2       3       4        집합 5개

 union(0, 1) — 0의 대표를 1 밑으로 매단다

   0 → 1           2       3       4        집합 4개

 union(1, 2) — 1의 대표를 2 밑으로 매단다

   0 → 1 → 2               3       4        집합 3개

 connected(0, 2) — 0에서 부모를 타고 올라가면 2, 2의 대표도 2 → 같은 무리

connected(0, 2)가 True인 게 이 자료구조의 매력이에요. 우리는 0과 2를 직접 합친 적이 없습니다. 0-1을 붙이고 1-2를 붙였을 뿐인데, 대표를 따라 올라가니 자동으로 같은 무리로 판정됩니다. 친구의 친구가 같은 네트워크에 속한다는 걸 따로 계산하지 않아도 되는 거죠.

count도 눈여겨보세요. 합칠 때마다 1씩 줄어 3이 됐습니다. 이 값이 곧 연결 요소의 개수예요. "그래프에 무리가 몇 개인가"를 묻는 문제라면 간선을 전부 union 한 뒤 count를 출력하면 끝입니다.

빅오와 이 버전의 약점

시간 복잡도를 따져 봅시다. find는 부모를 타고 루트까지 올라가니 트리 높이만큼 걸립니다. union은 find 두 번이니 같은 값이고요. 그러면 트리가 얼마나 높아질 수 있느냐가 관건인데, 이 버전은 최악 O(n) 입니다. 공간은 부모 배열 하나라 O(n) 이고요.

왜 최악이 O(n)일까요? union이 "높이를 안 보고 그냥 매달기" 때문입니다.

 union(0,1)  union(1,2)  union(2,3)  union(3,4) … 순으로 부르면

   0 → 1 → 2 → 3 → 4       한 줄로 늘어선 막대 트리

   find(0) 은 대표에 닿기까지 부모를 4번 밟는다
   원소가 n개면 n-1번 — 연결 리스트를 훑는 것과 다를 게 없다

트리를 쓰는 이유가 위로 빨리 올라가려는 건데, 한 줄로 늘어서면 트리인 의미가 사라집니다. B-2에서 배운 연결 리스트 인덱싱이 O(n)이었던 것과 똑같은 상황이 벌어진 거예요. 실제로 원소 1,000개를 저 순서로 합치면 트리 높이가 999가 되고, find(0)은 매번 999걸음을 밟습니다.

이 숫자 999를 없애는 게 Step 2와 Step 3의 목표입니다. 방향은 둘이에요. 이미 만들어진 긴 길을 사후에 없애거나(경로 압축), 애초에 길어지지 않게 막거나(union by rank).

기댈 내장이 없다

지금까지 우리는 늘 두 트랙으로 배웠죠. C-2에서 힙을 직접 짜고 실전에선 heapq를, D-2에서 이진 탐색을 직접 짜고 실전에선 bisect를 쓰라고 했습니다.

그런데 분리 집합은 파이썬 표준 라이브러리에 없습니다. 대조할 내장이 아예 없어요. 그래서 여기서는 직접 구현이 곧 실전입니다. 코딩테스트에서 유니온 파인드가 필요하면 오늘 배울 20줄 남짓을 손으로 적는 게 표준 풀이예요.

거꾸로 보면 반가운 소식이기도 합니다. 외울 코드가 짧고, 한 번 익히면 변형 없이 그대로 재사용되거든요. 오늘 Step 3까지 가면 그 20줄이 완성됩니다.

💡 한 줄 정리

"이 둘이 같은 무리인가"를 반복해서 물어야 하는 상황에서는 매번 DFS/BFS로 훑는 대신 무리를 계속 들고 있는 분리 집합을 쓴다. 집합마다 대표 하나를 두고 부모 포인터로 이으면 집합이 트리가 되며, 최적화 없는 원형은 막대 트리 탓에 find·union이 최악 O(n)·공간 O(n)이다. 파이썬 표준 라이브러리에는 분리 집합이 없어 직접 구현이 곧 실전 풀이다.

Step 2: "경로를 압축해서 빠르게" (~20분)

Step 1이 남긴 숙제는 숫자 하나로 요약됩니다. 999. 원소 1,000개를 한 줄로 이어 붙였더니 트리 높이가 999가 됐고, find(0)을 부를 때마다 부모 포인터를 999번 밟아야 했어요.

그런데 여기서 조금 억울한 생각이 듭니다. 999걸음을 힘들게 밟아 대표가 누구인지 이미 알아냈잖아요. 그런데 그 결과를 어디에도 안 적어 두고 그냥 버립니다. 그러니 다음에 또 물으면 999걸음을 처음부터 다시 밟죠.

발상은 여기서 나옵니다. 어차피 루트까지 올라갔으니, 올라가며 지나친 원소들을 전부 루트에 직접 매달아 두자. 길을 한 번 훑을 때마다 그 길이 사라지는 셈이에요. 이걸 경로 압축(path compression) 이라고 부릅니다.

find만 바꾼다

여기가 이 Step의 학습 포인트인데, 바뀌는 게 find 하나뿐입니다. union도 connected도 손대지 않아요. 그래서 코드도 Step 1의 클래스를 그대로 물려받고 find만 다시 씁니다.

class PathCompressedUnionFind(NaiveUnionFind):
    """경로 압축만 얹은 버전. find는 사실상 평균 O(log n)·공간 O(n)."""

    def find(self, x):
        """대표를 찾고, 지나온 원소를 전부 대표 밑으로 옮긴다. 분할 상환 O(log n)."""
        root = x
        while self.parent[root] != root:        # ① 먼저 루트를 찾고
            root = self.parent[root]
            self.steps += 1
        while self.parent[x] != root:           # ② 지나온 길을 루트에 직접 매단다
            self.parent[x], x = root, self.parent[x]
        return root

find가 두 단계로 나뉜 게 보이시죠.

① 먼저 루트를 찾습니다. Step 1의 find와 완전히 같은 반복문이에요. x 대신 root라는 변수를 쓰는 게 유일한 차이인데, 이유가 있습니다. ②에서 출발점 x부터 다시 훑어야 하니, x를 원래 값 그대로 남겨 둬야 하거든요.

② 지나온 길을 루트에 매답니다. self.parent[x], x = root, self.parent[x] 이 한 줄이 조금 낯설 텐데, 파이썬의 다중 할당은 오른쪽을 먼저 전부 계산한 뒤 왼쪽에 넣습니다. 그러니 "원래 부모를 기억해 뒀다가 → x의 부모를 루트로 바꾸고 → 기억해 둔 원래 부모로 이동"이 한 줄에 일어나요. 순서를 바꿔 두 줄로 쓰면 다음에 갈 곳을 잃어버립니다.

 경로 압축 — 루트까지 올라간 김에, 지나온 원소를 전부 루트에 직접 매단다

   압축 전
     0 → 1 → 2 → 3 → 4
     find(0) 은 부모 포인터를 4번 밟는다

   find(0) 을 한 번 부른 뒤
     0 → 4    1 → 4    2 → 4    3 → 4
     이제 누구를 find 해도 한 걸음이면 끝난다

첫 호출은 이득이 없다

여기가 이 Step의 백미입니다. 경로 압축을 얹으면 얼마나 빨라지느냐고 물으면, 정답은 "첫 호출은 하나도 안 빨라진다" 예요.

당연합니다. 루트를 찾으려면 어차피 999걸음을 밟아야 하니까요. 압축은 그 위에 얹히는 작업이라, 첫 호출은 오히려 일이 조금 더 많습니다. 이득은 두 번째 호출부터 옵니다.

원소 1,000개를 union(0,1), union(1,2) … 순서로 이어 붙인 뒤 실제로 재 보면 이렇습니다.

마지막 줄의 1,008을 뜯어보세요. 999 + 1 × 9 입니다. 첫 호출에서 999를 정직하게 다 내고, 그 뒤 아홉 번은 1걸음씩만 낸 거예요. 999걸음짜리 길이 첫 호출 한 번으로 영구히 사라졌기 때문입니다.

이렇게 한 번 비싸게 치르고 그 뒤로 계속 싸게 쓰는 구조를 분할 상환(amortized) 이라고 부릅니다. 한 번의 최악 비용만 보면 O(n)이라 나빠 보이지만, 호출 횟수로 나눈 평균을 보면 훨씬 작아요. 신문 구독료를 1년치 한 번에 내면 그날 지출은 크지만 하루치로 나누면 얼마 안 되는 것과 같은 셈법입니다.

그래서 경로 압축의 복잡도는 최악 한 번이 아니라 분할 상환 O(log n) 으로 적습니다. 공간은 여전히 부모 배열뿐이라 O(n) 이고요. 배열 하나 안 늘리고 반복문 세 줄로 O(n)을 O(log n)으로 낮춘 셈이니, 가성비가 대단하죠.

다만 아직 절반이다

표의 첫 줄을 다시 보세요. 합치고 난 직후 트리 높이는 여전히 999입니다.

경로 압축은 이미 만들어진 긴 길을 사후에 없앨 뿐이라, union이 막대 트리를 만드는 것 자체는 막지 못하거든요. 만약 문제가 find를 거의 안 부르고 union만 잔뜩 부른다면, 압축이 일어날 기회가 없어 999짜리 트리가 그대로 남습니다.

그래서 나머지 절반이 필요합니다. 만들어지는 것 자체를 막는 쪽이요. 그게 Step 3의 union by rank입니다.

💡 한 줄 정리

경로 압축은 find로 루트까지 올라간 김에 지나온 원소를 전부 루트에 직접 매다는 기법이며, union은 그대로 두고 find만 바꾸면 된다. 첫 호출은 999걸음으로 이득이 없지만 그 한 번이 길을 없애 두 번째부터 1걸음이 되는 분할 상환 O(log n)·공간 O(n) 구조다. 다만 이미 생긴 길을 사후에 없앨 뿐이라 막대 트리가 만들어지는 것 자체는 막지 못한다.

if parent[x] == x: return x
parent[x] = find(parent[x])
return parent[x]

Step 3: "합칠 때도 영리하게" (~20분)

Step 2가 남긴 숙제는 분명합니다. 경로 압축은 이미 생긴 긴 길을 없앨 뿐이니, 이번엔 생기지 않게 막을 차례예요.

원인은 Step 1에서 이미 지목해 뒀습니다. union이 self.parent[root_a] = root_b로 높이를 안 보고 그냥 매달기 때문이었죠. 높은 트리를 낮은 트리 밑에 붙여 버리면 전체 높이가 1 늘어납니다. 반대로 낮은 쪽을 높은 쪽 밑에 넣으면 어떨까요? 높은 쪽이 그대로 루트가 되니 높이가 아예 안 늘어납니다.

이 규칙이 union by rank 예요. rank는 그 트리의 높이 상한을 대충 적어 둔 값입니다.

 높이가 다른 둘을 합칠 때 — 낮은 쪽을 높은 쪽 밑으로

   합치기 전                합친 뒤
     a (rank 1)              a (rank 1)   ← rank 그대로
     └ b                     ├ b
                             └ c
     c (rank 0)

 높이가 같은 둘을 합칠 때 — 이때만 rank가 1 오른다

   합치기 전                합친 뒤
     a (rank 1)              a (rank 2)   ← 여기서만 오른다
     └ b                     ├ b
                             └ c
     c (rank 1)                 └ d
     └ d

"높이가 같을 때만 rank가 1 오른다" — 이 한 줄이 union by rank의 전부입니다. 그리고 여기서 아주 좋은 성질이 따라 나와요. rank를 1 올리려면 같은 높이의 트리가 둘 필요하니, 원소 수가 최소 배로 뛰어야 합니다. 그러니 높이는 log₂ n을 넘을 수가 없어요. 원소가 100만 개여도 높이는 20 이하입니다.

코드로 확인하기

실전에서 쓰는 버전이 바로 이 클래스입니다. find는 Step 2의 경로 압축과 논리가 똑같아서 생략하고, 달라진 부분만 보겠습니다.

class UnionFind:
    """경로 압축 + union by rank. 두 연산 모두 사실상 O(α(n)) ≈ 상수·공간 O(n)."""

    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n             # 트리 높이의 상한. 처음엔 전부 0
        self.count = n
        self.steps = 0                  # 학습용 계측기

    def union(self, a, b):
        """낮은 트리를 높은 트리 밑에 매단다. 이미 같은 집합이면 False. O(α(n))."""
        root_a, root_b = self.find(a), self.find(b)
        if root_a == root_b:
            return False
        if self.rank[root_a] < self.rank[root_b]:
            root_a, root_b = root_b, root_a         # root_a가 늘 높은(같은) 쪽이 되게
        self.parent[root_b] = root_a                # 낮은 쪽을 높은 쪽 밑으로
        if self.rank[root_a] == self.rank[root_b]:
            self.rank[root_a] += 1                  # 높이가 같을 때만 1 올라간다
        self.count -= 1
        return True

root_a, root_b = root_b, root_a 이 한 줄이 요령입니다. 조건 분기를 두 갈래로 쓰는 대신, root_a가 항상 높은 쪽(또는 같은 쪽)이 되도록 둘을 맞바꿔 두는 거예요. 그러면 그 아래 두 줄은 갈래를 따질 필요 없이 한 가지 경우만 처리하면 됩니다. 코드가 짧아지고 실수할 여지도 줄어들죠.

self.rank[root_a] == self.rank[root_b] 비교가 맞바꾼 뒤에 오는 것도 눈여겨보세요. 서로 맞바꿔도 두 값이 같다면 원래도 같았다는 뜻이니, 이 위치에서 비교해도 아무 문제가 없습니다.

"naive는 항상 느리다"는 틀린 말입니다

여기서 아주 중요한 대조를 하나 하고 갈게요. 최적화를 얹었으니 이제 원형보다 항상 빠르겠거니 생각하기 쉬운데, 그렇지 않습니다.

먼저 좋은 소식입니다. Step 1에서 높이 999짜리 막대 트리를 만들던 바로 그 순서 — union(i, i+1)을 1,000번 — 를 그대로 먹여도 이 버전의 트리 높이는 1 입니다. 999가 1이 됐어요.

그런데 rank를 최대로 밀어 올리는 순서로 몰아붙이면 어떨까요? 같은 높이의 트리끼리만 짝지어 합치는 순서로 원소 1,024개를 넣으면 이렇게 나옵니다.

아래 줄을 보세요. 둘이 같습니다. 10은 정확히 log₂ 1024예요. 이 순서에서는 원형도 알아서 균형 잡힌 트리를 만들거든요.

그러니까 원형의 결함은 "평균적으로 느리다"가 아닙니다. 운이 좋으면 원형도 높이 10짜리 좋은 트리를 만들어요. 진짜 결함은 한 줄로 늘어서는 최악의 순서를 막지 못한다는 데 있습니다. 입력이 어떻게 들어오느냐에 성능을 통째로 맡기고 있는 거죠.

union by rank의 존재 이유가 정확히 여기입니다. 평균을 끌어올리는 게 아니라 최악을 봉쇄하는 것. 어떤 순서로 union이 들어와도 높이가 log₂ n을 넘지 못하도록 잠가 버립니다. 코딩테스트에서 "저격 데이터"라 불리는 최악 입력이 문제 세트에 흔히 섞여 있다는 걸 생각하면, 이 보증이 얼마나 값진지 아시겠죠.

rank 대신 size를 세는 갈래

같은 발상을 높이 대신 원소 개수로 해도 됩니다. 작은 트리를 큰 트리 밑에 매다는 거예요. 큰 쪽에 붙이면 옮겨지는 원소가 적은 쪽뿐이라는 논리도 같아서, 높이는 마찬가지로 log₂ n에 묶입니다.

class UnionFindBySize(UnionFind):
    """경로 압축 + union by size. 복잡도는 UnionFind와 같고, 집합 크기를 덤으로 준다."""

    def __init__(self, n):
        super().__init__(n)
        self.size = [1] * n             # 각 집합의 원소 개수. 처음엔 전부 혼자

    def union(self, a, b):
        """작은 트리를 큰 트리 밑에 매단다. 이미 같은 집합이면 False. O(α(n))."""
        root_a, root_b = self.find(a), self.find(b)
        if root_a == root_b:
            return False
        if self.size[root_a] < self.size[root_b]:
            root_a, root_b = root_b, root_a         # root_a가 늘 큰 쪽이 되게
        self.parent[root_b] = root_a
        self.size[root_a] += self.size[root_b]      # 흡수한 만큼 크기를 더한다
        self.count -= 1
        return True

    def size_of(self, x):
        """x가 속한 집합의 원소 개수. O(α(n))."""
        return self.size[self.find(x)]

구조가 rank 버전과 거의 판박이죠. 비교 기준이 rank에서 size로 바뀌고, "높이가 같을 때만 +1" 대신 "흡수한 만큼 더하기" 가 들어갔을 뿐입니다.

그러면 둘 중 뭘 골라야 할까요? 성능으로는 구분이 안 됩니다. 갈라 쓰는 기준은 딱 하나예요. "집합 크기가 답에 필요한가."

size는 합칠 때 더해 두기만 하면 언제든 size_of로 꺼내 쓸 수 있습니다. 반면 rank는 경로 압축 때문에 실제 높이와 어긋나는 근삿값이라 그런 용도로 못 써요. 압축이 트리를 납작하게 만들어도 rank는 줄지 않거든요. 어차피 높이 상한으로만 쓰니 문제가 없을 뿐입니다.

🌟 실전 기본값: 코딩테스트에서는 size 버전을 쓰는 사람이 많습니다. "가장 큰 무리의 인원", "친구 네트워크 크기"처럼 크기를 묻는 문제가 잦은데, size를 쓰면 그 질의가 공짜로 딸려 오거든요. 성능이 같으니 정보가 더 나오는 쪽을 기본으로 두는 셈입니다.

사이클 검사가 세 줄로 끝난다

Step 1에서 심어 둔 복선을 이제 회수하겠습니다. union이 False를 돌려주면 "이 둘은 원래 이어져 있었다" 는 뜻이라고 했죠.

그 신호 하나로 사이클 검사가 끝납니다.

def has_cycle(num_vertices, edges):
    """무방향 그래프에 사이클이 있나. O(E·α(V)) 시간·O(V) 공간."""
    uf = UnionFind(num_vertices)
    for u, v in edges:
        if not uf.union(u, v):          # 합칠 게 없다 = 이미 이어져 있었다 = 사이클
            return True
    return False

간선을 하나씩 집어 양 끝을 union 해 보는 게 전부예요. union이 False를 냈다면 그 두 정점은 이 간선 없이도 이미 이어져 있었다는 뜻이고, 그러면 기존 길과 이 간선이 고리를 이룹니다. 사이클이죠.

 (0,1) 합침   (1,2) 합침   (2,0) → 0과 2는 이미 한 집합 → 사이클

돌려 보겠습니다.

has_cycle(3, [(0,1), (1,2), (2,0)])   → True    # 삼각형
has_cycle(4, [(0,1), (0,2), (1,3)])   → False   # 트리
has_cycle(6, [(0,1), (1,2), (3,4)])   → False   # 숲
has_cycle(3, [(1,1)])                 → True    # 자기 루프

세 번째를 눈여겨보세요. 정점 6개가 {0,1,2} {3,4} {5} 세 덩어리로 흩어져 있는데도 False입니다. 사이클은 덩어리마다 따로 판정되는 게 아니라 간선 하나하나가 고리를 닫는지만 보면 되니까요. 이렇게 사이클 없는 여러 덩어리를 숲(forest)이라고 부릅니다. 네 번째 자기 루프 (1,1)도 union(1,1)이 곧바로 False라 잡힙니다.

E-2의 DFS로도 사이클은 잡을 수 있어요. 그런데 유니온 파인드가 나은 상황이 분명히 있습니다. 간선이 하나씩 도착하는 상황이에요. 간선이 올 때마다 그래프 전체를 다시 훑을 필요 없이 union 한 번으로 판정이 끝나거든요. Step 1에서 봤던 "질의가 계속 들어온다"는 그 상황 그대로입니다.

그리고 이 판정이 오늘 후반부 크루스칼의 심장입니다. 가중치가 작은 간선부터 집으면서 "사이클을 닫지 않는 간선만" 채택하면 그게 곧 최소 신장 트리가 돼요. 오늘 이 세 줄을 다시 만나게 되니 눈에 익혀 두세요.

빅오 총정리

세 버전을 한 표에 놓고 비교하겠습니다.

마지막 칸의 α(n) 은 역아커만 함수라고 읽습니다. 아커만 함수라는, 값이 상상 이상으로 급하게 커지는 함수의 역함수인데, 그래서 α는 반대로 지독하게 천천히 커져요. 얼마나 느리냐면 n이 우주의 원자 수쯤 되어도 5를 넘지 않습니다. 현실의 어떤 입력에서도 5 이하라, 그냥 사실상 상수로 봐도 됩니다.

"1초에 약 1억 연산" 잣대를 대 보면 이 자료구조는 사실상 제한이 없어요. 간선 수십만~100만 개를 훑으면서 매번 union과 find를 불러도 넉넉히 통과합니다. 그래프 문제에서 유니온 파인드가 병목이 되는 경우는 거의 없다고 보셔도 좋아요.

has_cycle은 간선마다 union 한 번이니 시간 O(E·α(V)), 부모·rank 배열만 들고 있어 공간 O(V) 입니다.

🎯 코테에서는 이렇게 나옵니다: "네트워크가 몇 개로 연결되어 있는가"(간선을 전부 union 하고 count 출력), "친구 관계로 묶인 그룹의 수와 가장 큰 그룹의 크기"(UnionFindBySize + size_of), "섬의 개수"(격자에서 인접한 땅끼리 union). 문제에 "같은 그룹인가", "몇 개의 무리로 나뉘나", "연결되어 있는가" 라는 말이 보이면 유니온 파인드를 먼저 떠올리세요.

💡 한 줄 정리

union by rank는 낮은 트리를 높은 트리 밑에 매달고 높이가 같을 때만 rank를 1 올려 트리 높이를 log₂ n에 묶는다. 최적화 없는 원형이 늘 느린 게 아니라 최악의 합치기 순서를 막지 못하는 것이 결함이고, rank는 바로 그 최악을 봉쇄한다. 경로 압축까지 겹치면 사실상 O(α(n))이며, union이 False를 내는 신호만으로 사이클 검사가 세 줄에 끝난다.

Step 4: "가장 먼저 처리할 정점" (~20분)

지금까지 우리가 그래프에 던진 질문은 "이 둘이 같은 무리인가"였습니다. 이제 질문을 바꿔 볼게요. "어떤 것을 먼저 해야 하나?"

이 질문은 도처에 있습니다. 자료구조를 들어야 알고리즘을 들을 수 있는 선수 과목, A를 컴파일해야 B를 컴파일할 수 있는 빌드 의존성, 앞 공정이 끝나야 다음 공정이 시작되는 작업 스케줄, 셀 하나가 바뀌면 그걸 참조하는 셀들이 다시 계산되는 엑셀 수식까지요. 공통점이 보이시나요? 전부 방향 간선이 "이게 먼저"를 뜻한다는 겁니다.

 선수 과목 그래프 — 화살표는 "이게 먼저"를 뜻한다

    자료구조 ──> 알고리즘 ──> 코딩테스트
        │                        ^
        └──────> 파이썬 ─────────┘

이렇게 얽힌 정점들을 한 줄로 세우는 것, 그것도 모든 화살표가 왼쪽에서 오른쪽으로만 향하도록 세우는 것을 위상 정렬(topological sort)이라고 부릅니다. 정확히 말하면 모든 간선 u→v에 대해 u가 v보다 앞에 오도록 정점을 일렬로 늘어놓는 것이에요.

여기엔 조건이 하나 붙습니다. 그래프에 사이클이 있으면 답이 아예 없어요. A가 B보다 앞이고 동시에 B가 A보다 앞일 수는 없으니까요. 그래서 위상 정렬은 사이클 없는 방향 그래프에서만 성립하고, 그런 그래프를 DAG(Directed Acyclic Graph, 방향 비순환 그래프)라고 부릅니다.

진입 차수 0부터 꺼낸다

첫 번째 방법은 카흔(Kahn) 알고리즘입니다. 발상이 놀랄 만큼 상식적이에요. 선수 과목이 없는 과목부터 듣는다.

"선수 과목이 없다"를 그래프 용어로 옮기면 들어오는 간선이 하나도 없다가 됩니다. 이 들어오는 간선의 개수를 진입 차수(in-degree)라고 불러요. C-3에서 그래프를 인접 리스트로 담으면서 한 정점에 화살표가 몇 개 꽂히는지 세어 봤던 그 값입니다. 그때는 그래프의 성질을 보는 눈금 정도였는데, 오늘 열쇠로 쓰입니다.

 진입 차수 — 나에게 들어오는 화살표의 개수

   자료구조   0    ← 선수 과목이 없다. 지금 당장 들을 수 있다
   알고리즘   1    ← 자료구조를 들어야 한다
   파이썬     1    ← 자료구조를 들어야 한다
   코딩테스트 2    ← 알고리즘과 파이썬 둘 다 들어야 한다

진입 차수 0인 과목을 하나 듣고 나면 무슨 일이 벌어질까요? 그 과목을 선수로 두던 과목들의 조건이 하나씩 풀립니다. 그러다 진입 차수가 0이 되는 순간, 그 과목도 이제 들을 수 있게 되죠. 이 과정을 그대로 코드로 옮기면 됩니다.

# algorithms/topo_mst.py
def topological_sort_kahn(graph):
    vertices = _vertices(graph)
    in_degree = {v: 0 for v in vertices}
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1           # ① 들어오는 간선을 센다

    # ② 선수 과목이 없는 정점부터 — BFS의 시작 정점 자리에 해당한다
    queue = deque(v for v in vertices if in_degree[v] == 0)

    order = []
    while queue:
        node = queue.popleft()          # ③ 앞에서 꺼낸다(FIFO) — BFS와 똑같다
        order.append(node)
        for nxt in graph.get(node, []):
            in_degree[nxt] -= 1         # 이 정점을 들었으니 선수 조건 하나가 풀린다
            if in_degree[nxt] == 0:     # ④ 선수 과목을 전부 채웠다 = 이제 들을 수 있다
                queue.append(nxt)

    if len(order) != len(vertices):
        return []                       # 다 못 꺼냈다 = 사이클이 있다
    return order

graph는 {정점: [다음 정점, ...]} 형태의 방향 그래프입니다. E-2에서 DFS·BFS를 돌리던 그 인접 리스트와 똑같은 모양이고, 다만 화살표에 방향이 있다는 의미가 붙었어요.

이 코드, 어디서 본 것 같지 않나요

E-2에서 짠 BFS를 나란히 놓아 볼게요.

# algorithms/dfs_bfs.py — E-2에서 짠 BFS
def bfs(graph, start):
    visited = {start}               # 큐에 넣는 순간 방문 표시(중복 인큐 방지)
    order = []
    queue = deque([start])
    while queue:
        node = queue.popleft()      # 앞에서 꺼낸다(FIFO)
        order.append(node)
        for nxt in graph.get(node, []):
            if nxt not in visited:
                visited.add(nxt)    # 꺼낼 때가 아니라 넣을 때 표시
                queue.append(nxt)
    return order

거의 같은 코드죠. deque에 넣고, while로 돌고, popleft()로 앞에서 꺼내고, 이웃을 훑어 조건이 맞으면 뒤에 붙입니다. 뼈대가 글자 단위로 겹쳐요.

 BFS와 카흔 — 골격은 같고 "큐에 넣을 자격"만 다르다

   BFS      꺼낸다 → 이웃 중 아직 방문 안 한 것을 큐에 넣는다
   카흔     꺼낸다 → 이웃의 진입 차수를 깎아 0 이 된 것을 큐에 넣는다

   둘 다:  deque + while + popleft  (시작점만 여럿일 수 있다)

딱 한 군데가 다릅니다. BFS는 if nxt not in visited로 큐에 넣을지 판단하고, 카흔은 if in_degree[nxt] == 0으로 판단해요. F-1에서 다익스트라가 "BFS의 큐를 우선순위 큐로 갈아 끼운 것"이었다면, 카흔은 BFS의 방문 검사를 진입 차수 검사로 갈아 끼운 것입니다. 새 알고리즘을 외우는 게 아니라 아는 골격에 부품 하나를 바꿔 끼우는 셈이에요.

시작점이 여럿일 수 있다는 점도 BFS와 다릅니다. BFS는 보통 정점 하나에서 출발하지만, 카흔은 진입 차수가 0인 정점을 전부 처음부터 큐에 넣고 시작해요.

사이클이면 빈 리스트

마지막 세 줄이 이 함수의 숨은 재주입니다.

    if len(order) != len(vertices):
        return []                       # 다 못 꺼냈다 = 사이클이 있다

사이클 위의 정점들은 서로가 서로를 기다립니다. A는 B를 기다리고 B는 A를 기다리니, 두 정점의 진입 차수가 영영 0이 되지 못해요. 큐에 들어갈 자격을 못 얻고, 그래서 결과에 정점이 다 차지 않습니다. "덜 나왔다"가 곧 사이클의 증거인 거죠. 정렬기가 사이클 검출기를 겸하는 겁니다.

돌려 보겠습니다.

위상 정렬(카흔): ['자료구조', '알고리즘', '파이썬', '코딩테스트']
사이클 그래프 카흔: []

첫 줄이 우리가 원하던 수강 순서예요. 두 번째는 {0: [1], 1: [2], 2: [0]}처럼 세 정점이 서로를 물고 도는 그래프인데, 빈 리스트가 나옵니다. 순서를 세울 방법이 없다는 뜻이에요.

답이 하나가 아니다

여기서 꼭 짚고 가야 할 게 있어요. 위상 정렬의 답은 유일하지 않습니다.

알고리즘과 파이썬 사이에는 선수 관계가 없죠. 어느 쪽을 먼저 들어도 상관없습니다. 그러니 ['자료구조', '알고리즘', '파이썬', '코딩테스트']도 맞고 ['자료구조', '파이썬', '알고리즘', '코딩테스트']도 맞아요. 진입 차수가 0인 정점이 큐에 여럿 들어 있을 때 어느 것을 먼저 꺼내느냐로 답이 갈리는 겁니다.

이건 알고리즘의 흠이 아니라 문제 자체의 성질이에요. 다음 Step에서 완전히 다른 방식으로 위상 정렬을 짜 볼 텐데, 같은 그래프에 다른 순서가 나옵니다. 그런데도 둘 다 정답이에요.

빅오를 따져 봅시다. 진입 차수를 세느라 간선을 한 번씩 훑고(E), 정점마다 한 번씩 꺼내며(V) 그 정점의 간선을 다시 한 번씩 훑습니다(E). 그래서 시간 O(V+E), 진입 차수표와 큐를 들고 있으니 공간 O(V)예요. 정점과 간선을 합쳐 한 번씩만 보는 거라 그래프 알고리즘 중에서도 가장 싼 축에 듭니다. 1초 1억 연산 잣대로 정점·간선 수백만 개까지 넉넉하게 통과해요.

💡 한 줄 정리

위상 정렬은 방향 그래프의 모든 간선 u→v에서 u가 앞에 오도록 정점을 일렬로 세우는 것이고, 사이클이 없는 DAG에서만 성립한다. 카흔 알고리즘은 진입 차수 0인 정점부터 꺼내며 이웃의 진입 차수를 깎는데, deque·popleft 골격이 E-2의 BFS와 같고 방문 검사가 진입 차수 검사로 바뀐 것만 다르다. 정점이 다 안 나오면 사이클이라 빈 리스트를 돌려주며, 시간 O(V+E)·공간 O(V)다.

Step 5: "깊게 내려가며 순서 정하기" (~20분)

카흔은 앞에서부터 세웠습니다. 선수 과목이 없는 것을 먼저 꺼내 왼쪽에 놓았죠. 이번엔 정반대로, 뒤에서부터 세워 보겠습니다.

발상은 이래요. 어떤 정점에서 갈 수 있는 데까지 끝까지 파고들어 봅니다. 더 갈 곳이 없어 돌아 나오는 순간, 그 정점을 기록해요. 그러면 기록되는 순서는 "더 이상 나갈 데가 없는 것"부터가 됩니다. 곧 맨 뒤에 와야 할 정점부터 쌓이는 거죠. 다 쌓고 나서 통째로 뒤집으면 위상 순서가 나옵니다.

E-1과 E-2에서 익힌 DFS 그대로예요. 다만 정점을 들어갈 때가 아니라 나올 때 기록한다는 점이 다릅니다. C-1의 트리 순회에서 배운 후위 순회가 이것이었죠.

def topological_sort_dfs(graph):
    visited = set()
    order = []

    def visit(node):
        visited.add(node)
        for nxt in graph.get(node, []):
            if nxt not in visited:
                visit(nxt)              # 갈 수 있는 데까지 먼저 파고든다
        order.append(node)              # 돌아 나오며 기록 = 후위 순회

    for v in _vertices(graph):
        if v not in visited:            # 어디서 시작해도 되지만 빠뜨리면 안 된다
            visit(v)

    order.reverse()                     # 먼저 끝난 것이 뒤로 가야 하므로 뒤집는다
    return order

왜 뒤집어야 하는지가 이 알고리즘의 전부입니다. 어떤 정점을 order에 붙이는 시점을 생각해 보세요. 그 정점이 가리키는 정점들은 이미 전부 기록돼 있습니다. 재귀가 먼저 다녀왔으니까요. 즉 "나보다 뒤에 와야 할 것들"이 나보다 먼저 쌓여요. 관계가 정확히 거꾸로 쌓이니 뒤집으면 제자리를 찾습니다.

 후위 순회로 쌓고 뒤집으면 위상 순서

   0 → 1 → 2   에서 0 부터 파고들면

     0 진입 → 1 진입 → 2 진입 → 2 는 갈 곳 없음 → 2 기록
                              → 1 로 돌아옴 → 1 기록
                              → 0 으로 돌아옴 → 0 기록

   쌓인 순서   [2, 1, 0]
   뒤집으면    [0, 1, 2]   ← 간선 방향과 맞는다

또 하나, 바깥 반복문에서 모든 정점을 훑는 이유도 짚고 갈게요. 그래프가 여러 덩어리로 나뉘어 있으면 한 정점에서 시작한 DFS가 전부를 훑지 못합니다. 그래서 아직 방문 안 한 정점이 남아 있으면 거기서 다시 시작해요. E-2의 count_components에서 덩어리마다 탐색을 새로 시작하던 것과 같은 처리입니다.

같은 그래프, 다른 답, 둘 다 정답

Step 4의 선수 과목 그래프에 두 함수를 나란히 돌려 보겠습니다.

위상 정렬(카흔): ['자료구조', '알고리즘', '파이썬', '코딩테스트']
위상 정렬(DFS):  ['자료구조', '파이썬', '알고리즘', '코딩테스트']

알고리즘과 파이썬의 순서가 뒤바뀌었죠. 그런데 두 답 모두 맞습니다. 둘 사이엔 선수 관계가 없어 어느 쪽을 먼저 들어도 되니까요. Step 4에서 예고한 대로 위상 정렬의 답은 하나가 아니라는 것이 눈으로 확인되는 대목이에요.

이건 코딩테스트에서 실제로 학생들을 괴롭히는 지점이기도 합니다. 내 답이 예제 출력과 다른데 틀린 게 아닐 수 있거든요. 문제가 "가능한 순서 중 아무거나"를 요구하면 채점기가 순서를 하나로 못 박지 않고 조건을 만족하는지만 검사합니다.

2색칠로는 못 잡는 것

카흔은 "정점이 다 안 나왔다"로 사이클을 알아챘습니다. DFS판에는 그런 장치가 없어요. 그래서 사이클 검출은 따로 짭니다. 그런데 이게 은근히 함정이 많은 코드예요.

가장 먼저 떠오르는 발상은 이겁니다. "이미 방문한 정점을 또 만나면 사이클이다." 방문/미방문 두 가지 색으로 칠하는 거죠. 그럴듯한데, 틀립니다.

 같은 정점을 다시 만났을 때 — 두 상황은 완전히 다르다

   ① 마름모 (사이클 없음)        ② 사이클 (0 → 1 → 2 → 0)

     0 ──→ 1                       0 ──→ 1
     │     │                       ↑     │
     ↓     ↓                       │     ↓
     2 ──→ 3                       └──── 2

   0 → 1 → 3 으로 내려갔다가        0 → 1 → 2 로 내려갔다가
   0 → 2 → 3 으로 3 을 또 만난다     2 → 0 으로 0 을 또 만난다

   두 번째로 만난 3 은              다시 만난 0 은
   "이미 다 보고 나온 곳"           "지금 내가 밟고 서 있는 길"
   = 사이클이 아니다                = 사이클이다

왼쪽 마름모 그래프를 보세요. {0: [1, 2], 1: [3], 2: [3], 3: []}입니다. 방향을 지키면 3에서 나가는 간선이 없어 어디로도 되돌아갈 수 없어요. 사이클이 아닙니다. 그런데 3을 두 번 만나긴 하죠. 2색칠은 그것만 보고 사이클이라고 오답을 냅니다. 무방향 그래프로 보면 고리처럼 보인다는 게 착시의 근원이에요.

그러니 물어야 할 질문은 "이미 만났나"가 아니라 "지금 내가 내려가는 길 위로 되돌아왔나"입니다. 이걸 구분하려고 색을 세 가지로 씁니다.

WHITE = 0       # 아직 방문 안 함
GRAY = 1        # 방문 중 — 지금 내려가는 길(재귀 스택) 위에 있다
BLACK = 2       # 방문 끝 — 이 아래는 전부 다 봤다


def has_cycle_directed(graph):
    color = {v: WHITE for v in _vertices(graph)}

    def visit(node):
        color[node] = GRAY                      # 이 길 위에 올라섰다
        for nxt in graph.get(node, []):
            if color[nxt] == GRAY:
                return True                     # 밟고 있는 길로 되돌아왔다 = 사이클
            if color[nxt] == WHITE and visit(nxt):
                return True
        color[node] = BLACK                     # 이 아래는 다 봤다 — 길에서 내려온다
        return False

    return any(visit(v) for v in color if color[v] == WHITE)

정점에 들어갈 때 GRAY로 칠하고, 그 정점 아래를 다 보고 나올 때 BLACK으로 바꿉니다. GRAY인 동안은 "지금 재귀 스택 위에 올라와 있다"는 뜻이에요. 내려가다 GRAY를 만나면 밟고 있는 길로 되돌아온 것이니 사이클입니다(이런 간선을 백간선, back edge라고 불러요). BLACK을 만나는 건 다른 길로 이미 다 살펴본 곳에 다시 닿았을 뿐이라 아무 문제가 없습니다.

자기 자신으로 가는 간선(0→0)도 자연스럽게 잡혀요. 자기가 GRAY인 채로 자기를 만나니까요.

실제로 돌려 보면 이렇습니다.

0→1→2→0 사이클?:   True
0→1, 1→2 사이클?:  False
자기 루프 0→0?:     True
0→1,0→2,1→3,2→3?:  False   (마름모 — 사이클 아님)

네 번째 줄이 오늘의 핵심입니다. 2색칠로 짰다면 여기서 True가 나와 조용히 틀렸을 거예요. F-1에서 음수 간선이 낀 다익스트라가 오류 없이 그럴듯한 숫자를 내던 것과 똑같은 종류의 위험입니다. 오류 메시지 없이 틀리는 코드가 가장 무섭습니다.

한 가지 더 정리하고 갈게요. 사이클 검출은 그래프의 방향 유무에 따라 도구가 완전히 갈립니다. 무방향 그래프는 유니온 파인드로 잡았죠(union이 False를 내면 사이클). 방향 그래프는 그 방법이 통하지 않고 3색칠이 필요합니다. 위 마름모가 정확히 그 차이를 보여 주는 예시예요.

두 트랙 — 이건 파이썬에 내장이 있다

원리를 손으로 짰으니 실전 이야기를 할 차례입니다. 위상 정렬은 파이썬 표준 라이브러리에 실제로 들어 있어요. graphlib.TopologicalSorter(Python 3.9부터)입니다.

다만 그냥 갖다 쓰면 헷갈리는 지점이 하나 있습니다. 입력의 방향이 우리 코드와 반대예요.

 입력 방향이 뒤집혀 있다

   우리 코드          {정점: [이 정점 다음에 올 것들]}
                      {"자료구조": ["알고리즘", "파이썬"]}

   TopologicalSorter  {정점: {이 정점보다 먼저 와야 할 것들}}   ← 선행자 그래프
                      {"알고리즘": {"자료구조"}}

우리는 "자료구조 다음에 알고리즘"이라고 적었는데, 표준 라이브러리는 "알고리즘 앞에 자료구조"라고 적습니다. 같은 관계를 반대편에서 서술하는 거예요. 여기서 그래프를 그대로 넣으면 순서가 통째로 뒤집힌 답이 나오니 조심하셔야 합니다. 그리고 사이클이 있으면 빈 리스트가 아니라 CycleError 예외를 던집니다.

🌟 판단 기준: 원리는 손으로 짜서 이해하고, 실무에서 의존성 순서를 풀 일이 생기면 graphlib을 쓰세요. 다만 코딩테스트에서는 대개 카흔을 직접 짜는 게 빠릅니다. 입력이 간선 목록으로 들어와서 어차피 그래프를 만들어야 하고, "사전순으로 출력" 같은 변형이 붙으면 내장으로는 손대기 어렵거든요.

카흔과 DFS, 무엇을 고르나

둘 다 시간 O(V+E)·공간 O(V)로 복잡도가 완전히 같습니다. 그러니 성능으로는 고를 수 없어요. 갈라 쓰는 기준은 곁다리로 얻는 것입니다.

코딩테스트 기본값은 카흔입니다. 사이클 판정이 공짜로 따라오고, 반복문이라 정점이 수십만 개로 깊어져도 재귀 깊이 제한을 걱정할 필요가 없어요. 파이썬 기본 재귀 깊이가 1000이라 E-1에서 배운 sys.setrecursionlimit을 매번 올려 줘야 하는 DFS판은 그만큼 실수 여지가 생깁니다.

💡 한 줄 정리

DFS 위상 정렬은 갈 수 있는 데까지 파고든 뒤 돌아 나오며 기록하고(후위 순회) 마지막에 뒤집는다. 같은 그래프에 카흔과 다른 순서가 나오지만 둘 다 정답이다. 방향 그래프의 사이클 검출은 WHITE·GRAY·BLACK 3색칠이 필요한데, 2색칠은 마름모 그래프를 사이클로 오판한다. 둘 다 O(V+E)·O(V)라 성능은 같고, 사이클 판정이 따라오고 재귀가 없는 카흔이 실전 기본값이다.

Step 6: "최장 경로도 순서가 있으면 답이다" (~20분)

지난 시간(F-1) 마지막에 한 학생이 이런 질문을 했습니다. "다익스트라로 최장 경로를 구하면 안 되나요? 부등호만 뒤집으면 될 것 같은데요." 그때 제가 이렇게 답하고 미뤄 뒀죠. 일반 그래프의 최장 경로는 NP-난해라 안 되지만, 사이클 없는 방향 그래프라면 풀린다. 그 순서를 만들어 주는 게 다음 시간에 배울 위상 정렬이라고요.

지금이 그 빚을 갚는 시간입니다. 방금 위상 순서를 손에 넣었으니, 미뤄 둔 질문에 답할 준비가 끝났어요.

왜 DAG에서는 풀리나

먼저 왜 일반 그래프에선 안 되는지 정리하고 갑시다. 이유는 두 겹이에요.

첫째, 사이클이 있으면 최장 경로라는 답 자체가 존재하지 않습니다. 사이클을 계속 돌면 길이를 얼마든지 늘릴 수 있으니까요. F-1의 음의 사이클이 최단 경로를 무너뜨리던 것과 정확히 거울상입니다.

둘째, 사이클이 없어도 다익스트라의 그리디는 못 씁니다. "가장 가까운 것을 꺼내면 확정"의 근거가 "더 걸어가 봐야 줄지 않는다"였는데, 최장에서는 더 걸어가면 길어지니까 확정할 근거가 사라져요.

그래서 그리디를 버리고 DP로 갑니다. dist[v]를 "v에서 끝나는 가장 긴 경로의 길이"로 두면 점화식이 한 줄이에요.

 DAG 최장 경로의 점화식

   dist[v] = max( dist[u] + w )      u → v 간선을 가진 모든 u 에 대해

   그런데 이 식을 계산하려면
     v 로 들어오는 모든 u 의 dist 가 이미 확정돼 있어야 한다
     → 그 순서를 만들어 주는 것이 정확히 위상 정렬이다

E-4·E-5에서 DP를 "작은 문제부터 채운다"로 배웠죠. 계단 오르기는 낮은 계단부터, 구간 DP는 짧은 구간부터 채웠습니다. 그래프에서 "작은 문제부터"의 정체가 바로 위상 순서예요. 오늘 배운 정렬이 DP의 채우는 순서로 곧장 들어가는 겁니다.

def longest_path_dag(graph, num_vertices):
    order = topological_sort_kahn(_strip_weights(graph, num_vertices))
    if num_vertices > 0 and not order:
        raise ValueError("사이클이 있는 그래프에는 최장 경로가 없다(무한히 길어진다)")

    dist = [0] * num_vertices           # 모든 정점이 출발점 후보라 0에서 시작
    previous = [None] * num_vertices

    for u in order:                     # 반드시 위상 순서로 — 여기가 이 알고리즘의 전부
        for v, weight in graph.get(u, []):
            if dist[u] + weight > dist[v]:      # 최단의 부등호를 뒤집은 것
                dist[v] = dist[u] + weight
                previous[v] = u                 # 이 정점으로 오는 가장 긴 길의 직전 정점
    if not dist:
        return 0, []

    end = max(range(num_vertices), key=lambda v: dist[v])   # 가장 길게 끝난 정점
    path = []
    node = end
    while node is not None:             # previous를 거꾸로 타고 출발점까지
        path.append(node)
        node = previous[node]
    path.reverse()
    return dist[end], path

세 군데를 짚을게요.

하나, 부등호가 뒤집혔습니다. if dist[u] + weight > dist[v]. F-1의 이완이 <였던 것과 딱 이 한 글자가 다릅니다. 학생 질문의 직관("부등호만 뒤집으면"), 절반은 맞았던 거예요. 나머지 절반은 위상 순서였고요.

둘, dist를 전부 0으로 시작합니다. F-1에서는 출발점만 0이고 나머지는 무한대였죠. 여기선 출발점을 정해 주지 않았습니다. 어디서 시작해 어디서 끝나든 가장 긴 것을 찾는 문제라, 모든 정점이 출발점 후보예요.

셋, 경로 복원이 F-1과 똑같습니다. previous[v] = u로 "누구를 거쳐 길어졌나"를 적어 두고, 끝에서 거꾸로 타고 올라가 뒤집습니다. F-1의 dijkstra_with_path에서 부모 배열로 최단 경로를 복원한 그 방식 그대로예요. E-4의 make_1, E-5의 LCS 복원까지 거슬러 올라가는 같은 기법입니다. 최적값을 구하는 DP를 짰다면 출처 배열 하나로 경로가 따라온다는 원칙이 또 통했습니다.

그리고 사이클이면 ValueError를 던집니다. 카흔이 빈 리스트를 돌려주는 것과 대비되는 처리인데, 이유는 잠시 뒤 질문 토글에서 다룰게요.

위상 순서를 빼면 얼마나 틀리나

"위상 순서로 훑어야 한다"는 말이 아직 추상적으로 들리실 겁니다. 숫자로 확인해 봅시다. 위 코드에서 딱 한 줄만 바꿔 볼게요.

def naive_longest_path(graph, num_vertices):
    dist = [0] * num_vertices
    previous = [None] * num_vertices

    for u in range(num_vertices):       # 위상 순서가 아니라 번호 순서 — 여기가 틀린 곳
        for v, weight in graph.get(u, []):
            if dist[u] + weight > dist[v]:
                dist[v] = dist[u] + weight
                previous[v] = u
    # 이하 최댓값 찾기와 경로 복원은 위와 글자 하나 다르지 않다

for u in order가 for u in range(num_vertices)로 바뀐 게 전부입니다. 위상 정렬을 부르지 않고 정점 번호 0, 1, 2, … 순서로 훑는 거죠. 그럴듯해 보이지 않나요?

이 그래프에 넣어 봅시다.

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

간선이 3→1로 거꾸로 나 있습니다. 위상 순서는 [0, 3, 1, 2]인데 번호 순서는 [0, 1, 2, 3]이라 두 순서가 어긋나요. 결과입니다.

위상 순서:         [0, 3, 1, 2]
최장 경로(정답):   (21, [0, 3, 1, 2])
번호 순서로 훑으면: (11, [0, 3, 1])

정답은 21인데 11이 나옵니다. 절반밖에 안 되는 답이에요.

어디서 틀렸는지 정확히 따라가 볼게요. 번호 순서니까 u=1을 u=3보다 먼저 봅니다. 그런데 그 시점에 dist[1]은 아직 0이에요. dist[1] = 11은 나중에 u=3을 볼 때야 확정되거든요. 그래서 1→2 간선에 10만 얹어 dist[2] = 10으로 계산해 버립니다. 나중에 dist[1]이 11로 갱신돼도 이미 지나간 1→2 간선을 다시 볼 기회는 없어요. 결국 최댓값이 dist[1] = 11로 나옵니다.

 확정되지 않은 값을 읽으면 벌어지는 일

   u=1 을 볼 때     dist[1] = 0   (아직 3 을 안 봤다)
                    → dist[2] = 0 + 10 = 10
   u=3 을 볼 때     dist[1] = 0 + 1 + 10 = 11  ← 이제야 확정
                    그런데 1 → 2 간선은 이미 지나갔다

   최종             dist = [0, 11, 10, 1]  →  최댓값 11
   정답             dist = [0, 11, 21, 1]  →  최댓값 21

여기서 흥미로운 성질 하나. 틀린 코드가 낸 [0, 3, 1]은 실재하는 경로입니다. 길이 11도 정확히 맞아요. 없는 길을 지어낸 게 아니라, 더 긴 길을 놓친 겁니다. 확정 안 된 값(항상 실제보다 작거나 같은 값)을 읽으니 언제나 과소평가 방향으로만 틀려요. 그래서 답을 넘어서는 일은 없고, 그만큼 눈치채기가 어렵습니다.

"돌려 보니 맞던데요"가 검증이 못 되는 이유

이 대목이 오늘 가장 중요한 교훈일지도 모르겠습니다. 같은 틀린 코드에 이런 그래프를 넣어 보세요.

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

   간선이 전부 작은 번호 → 큰 번호로 간다
   → 번호 순서 [0,1,2,3] 과 위상 순서 [0,1,2,3] 이 우연히 일치
   → 틀린 코드도 정답 15 를 낸다

멀쩡하게 정답이 나옵니다. 간선이 전부 작은 번호에서 큰 번호로 향하니 번호 순서가 곧 위상 순서거든요. 그리고 예제를 대충 만들면 이런 그래프가 나오기 쉽습니다. 사람이 그래프를 그릴 때 자연스럽게 0, 1, 2, 3 순서로 이어 놓으니까요.

그래서 "돌려 보니 맞더라"는 검증이 되지 못합니다. 이 코드는 순서가 어긋나는 그래프에서만 무너져요. 예제 세 개를 통과하고 제출했다가 채점기에서 틀리는 전형적인 상황이 여기서 나옵니다. 정점 4개짜리 그래프를 무작위로 만들어 재면 대략 셋 중 하나꼴로 틀린 답이 나오고, 정점이 6개면 그 비율이 더 올라갑니다.

⚠️ 알고리즘의 정당성은 예제가 아니라 논증으로 확인합니다. "이 값을 읽는 시점에 그 값이 확정돼 있는가"를 따져 보는 습관을 들이세요. E-5의 구간 DP에서 "짧은 구간부터 채워야 한다"고, F-1의 플로이드-워셜에서 "k가 반드시 가장 바깥"이라고 했던 것과 전부 같은 이야기입니다. DP는 채우는 순서가 곧 정확성입니다.

🎯 코테에선 이렇게 나온다

DAG 최장 경로는 지문에 "최장 경로"라고 안 적힌 채 나옵니다. 대표 얼굴이 작업 스케줄링이에요.

여러 작업이 있고 각 작업에 걸리는 시간이 있으며 선후 관계가 정해져 있을 때, 전체를 끝내는 데 걸리는 최소 시간을 묻는 문제입니다. 얼핏 최단 같은데 실은 최장이에요. 병렬로 진행되는 작업들 중 가장 오래 걸리는 사슬이 전체 완료 시각을 결정하니까요. 이 사슬을 임계 경로(critical path)라고 부르고, 프로젝트 관리에서 실제로 쓰는 용어입니다.

지문에 "선행 작업", "동시에 진행할 수 있다", "전체가 끝나는 최소 시간"이 보이면 위상 정렬 + DP를 떠올리시면 됩니다.

빅오는 시간 O(V+E)입니다. 위상 정렬이 O(V+E)이고 그 뒤 DP가 간선을 한 번씩 훑어 O(V+E)라 합쳐도 O(V+E)예요. 공간은 dist와 previous 배열로 O(V)입니다. 최단 경로의 다익스트라가 O(E log V)였던 것과 비교하면 오히려 더 싸요. 힙이 필요 없거든요. 조건이 까다로운 대신(DAG여야 한다) 값은 더 싸게 치른다는 트레이드오프입니다.

💡 한 줄 정리

일반 그래프의 최장 경로는 NP-난해지만, DAG라면 위상 순서대로 dist[v] = max(dist[u] + w)를 채우는 DP로 O(V+E)에 풀린다. 부등호를 뒤집는 것이 절반이고 나머지 절반이 위상 순서인데, 순서를 정점 번호로 바꾸면 아직 확정 안 된 값을 읽어 과소평가된 답을 조용히 낸다. 경로 복원은 F-1의 부모 배열 역추적과 같고, 코테에서는 작업 스케줄링·임계 경로로 등장한다.

Step 7: "가장 가벼운 간선부터" (~20분)

오늘의 마지막 질문으로 넘어갑니다. 지금까지 "같은 무리인가", "어떤 순서인가"를 물었죠. 이번엔 이겁니다. "전부 잇는 데 드는 최소 비용은?"

마을 n개에 도로를 깔아 모든 마을이 오갈 수 있게 만들되, 공사비를 최소로 하고 싶다고 해 봅시다. 통신망 케이블, 전력망, 상수도관도 똑같은 문제예요.

먼저 도로를 몇 개나 깔아야 하는지부터 따져 볼까요. 마을이 4개면 3개, 10개면 9개입니다. n개를 잇는 데는 n-1개면 충분해요. 하나라도 더 놓으면 사이클이 생기는데, 사이클 위의 도로 하나를 빼도 여전히 전부 이어져 있으니 그건 낭비입니다.

 신장 트리 — 모든 정점을 잇되 사이클이 없는 부분 그래프

   원래 그래프 (간선 5개)        신장 트리 (간선 3개 = V-1)

     0 --- 1                       0 --- 1
     | \   |                             |
     |  \  |            →                |
     3 --- 2                       3 --- 2

   4 개 정점을 전부 잇는 데 간선 3 개면 충분하다
   하나라도 더 놓으면 사이클이 생겨 낭비다

이렇게 모든 정점을 포함하면서 사이클이 없는 부분 그래프를 신장 트리(spanning tree)라고 부릅니다. "펼쳐서 전부 덮는 트리"라는 뜻이에요. 간선은 언제나 정확히 V-1개입니다. 그리고 신장 트리는 보통 여러 개인데, 그중 간선 가중치 합이 가장 작은 것이 최소 신장 트리(MST, Minimum Spanning Tree)예요.

컷 성질 — 왜 싼 것부터 집어도 되나

MST를 구하는 두 알고리즘은 둘 다 E-3의 그리디입니다. 그런데 E-3에서 우리는 그리디가 거스름돈 문제에서 보기 좋게 깨지는 걸 봤죠. 그러니 이번에도 왜 이 그리디는 안 깨지는지부터 따져야 합니다.

근거는 컷 성질(cut property)입니다.

 컷 성질 — 어떤 경계든, 그 경계를 건너는 간선 중 가장 싼 것은
           반드시 어떤 최소 신장 트리 안에 들어간다

   정점을 두 덩어리로 가른다      S = {0, 1}      바깥 = {2, 3}

   경계를 건너는 간선             1-2 (2)   0-3 (5)   1-3 (9)

   그중 가장 싼 것                1-2 (2)   ← 이건 집어도 절대 손해가 없다

   왜?  1-2 가 없는 MST 에 1-2 를 억지로 넣으면 사이클이 하나 생긴다
        그 사이클에도 경계를 건너는 간선이 반드시 하나 더 있다 (0-3 이나 1-3)
        그건 1-2 보다 비싸거나 같다
        그것을 빼고 1-2 를 넣으면 총합이 줄거나 같다 → 여전히 MST

정점을 어떻게 두 덩어리로 가르든 상관없습니다. 그 경계를 건너는 간선 중 가장 싼 것은 안심하고 집어도 돼요.

증명의 뼈대가 익숙하지 않나요? "최적해에 내 선택이 없다고 치자 → 바꿔치기해도 손해가 없다 → 그러니 내 선택을 포함하는 최적해가 존재한다." E-3에서 배운 교환 논법입니다. F-1에서 다익스트라의 "미확정 중 최소를 꺼내면 확정"을 정당화한 것도 같은 논법이었고요. 그리디는 이 논법을 통과할 때만 쓴다는 원칙이 오늘도 그대로입니다.

크루스칼 — 전역에서 싼 것부터

컷 성질을 가장 단순하게 써먹는 방법이 크루스칼(Kruskal)입니다. 간선을 가중치 오름차순으로 전부 정렬해 놓고, 싼 것부터 차례로 집어요. 단 사이클을 닫는 간선만 버립니다.

def kruskal(num_vertices, edges):
    uf = UnionFind(num_vertices)
    total = 0
    selected = []

    for u, v, weight in sorted(edges, key=lambda e: e[2]):   # 가중치 오름차순
        if uf.union(u, v):              # True = 원래 따로였다 = 사이클을 안 닫는다
            total += weight
            selected.append((u, v, weight))
            if len(selected) == num_vertices - 1:
                break                   # 간선 V-1개면 트리 완성 — 남은 간선은 볼 것 없다
    return total, selected

Step 3에서 제가 유니온 파인드의 union이 True/False를 돌려주는 걸 두고 "이것이 크루스칼의 심장"이라고 했죠. 지금 회수합니다.

if uf.union(u, v): 이 한 줄을 보세요. union이 True를 돌려주면 두 정점이 원래 따로 있던 무리라는 뜻이고, 곧 이 간선은 사이클을 닫지 않는다는 뜻입니다. 그러면 그대로 집으면 돼요. False면 이미 같은 무리라 이 간선은 사이클을 닫으니 건너뜁니다. 판정과 합치기가 함수 호출 한 번에 동시에 끝나는 것, 이게 이 조합의 아름다움이에요.

만약 union이 아무것도 안 돌려줬다면 이렇게 써야 했을 겁니다. if not uf.connected(u, v): uf.union(u, v) — find를 네 번 부르게 되죠. 반환값 하나 설계한 덕에 절반이 줄었습니다.

크루스칼이 컷 성질을 쓰는 방식도 짚어 둘게요. 지금 집으려는 간선이 잇는 두 덩어리, 그게 곧 경계입니다. 그보다 싼 간선은 이미 다 봤으니 이 간선이 그 경계를 건너는 가장 싼 것이고, 컷 성질이 이걸 집어도 된다고 보증합니다.

돌려 보겠습니다. 정사각형 네 변이 전부 1이고 대각선 하나가 3인 그래프예요.

     0 --(1)-- 1
     |  \      |
    (1)  (3)  (1)
     |      \  |
     3 --(1)-- 2

크루스칼: 3 [(0, 1, 1), (1, 2, 1), (2, 3, 1)]

가중치 1짜리 변 셋을 집고 끝났습니다. 총 3이에요. 마지막 변(3-0)과 대각선(0-2)은 사이클을 닫으니 버려졌죠. 그리고 간선 3개(= V-1)를 모은 순간 break로 조기 종료합니다. 트리가 완성됐는데 남은 간선을 볼 이유가 없으니까요.

이어져 있지 않으면 어떻게 되나

그래프가 여러 덩어리로 나뉘어 있으면 트리가 아니라 숲(spanning forest)이 나옵니다. 크루스칼은 이 경우에도 아무 불평 없이 각 덩어리의 MST를 만들어 줘요.

비연결 크루스칼: 3 [(0, 1, 1), (2, 3, 2)]
간선이 V-1개인가: False        ← 이어져 있지 않다는 판정법

{0,1}과 {2,3}이 따로 노는 그래프입니다. 간선이 2개밖에 안 나왔죠. 정점이 4개면 트리는 간선이 3개여야 하는데요.

그래서 연결 여부를 확인하는 방법이 여기서 나옵니다. len(선택된 간선) == num_vertices - 1인지 보면 돼요. V-1개가 안 되면 그래프가 이어져 있지 않다는 뜻입니다. 코딩테스트에서 "모든 도시를 연결할 수 없으면 -1을 출력하라" 같은 조건이 붙으면 이 한 줄로 판정하시면 됩니다.

빅오를 따져 봅시다. 시간 O(E log E)인데, 흥미로운 건 이 비용의 거의 전부가 정렬이라는 점이에요. 정렬 뒤에는 간선마다 union을 한 번씩 부르는데, Step 3에서 확인했듯 이게 사실상 상수 시간(O(α(V)))이라 전부 합쳐도 O(E·α(V))입니다. 정렬의 O(E log E)에 완전히 묻혀요. 크루스칼의 정체는 "정렬 + 거의 공짜인 사이클 검사"인 셈입니다.

공간은 유니온 파인드의 부모·rank 배열로 O(V)입니다. 1초 1억 연산 잣대로 간선 수십만 개까지 넉넉해요. 참고로 E ≤ V²이므로 log E ≤ 2 log V라, O(E log V)로 적어도 같은 말입니다.

💡 한 줄 정리

신장 트리는 모든 정점을 잇되 사이클이 없는 부분 그래프로 간선이 정확히 V-1개이고, 그중 가중치 합이 최소인 것이 MST다. 컷 성질(어떤 경계든 건너는 가장 싼 간선은 어떤 MST에 반드시 있다)이 그리디를 정당화하며, 근거는 E-3의 교환 논법이다. 크루스칼은 간선을 가중치 순으로 정렬해 union이 True인 것만 집는데, 시간 O(E log E)로 정렬이 지배하고 공간은 O(V)다.

Step 8: "정점부터 자라나게" (~20분)

크루스칼은 그래프 전체를 내려다보며 싼 간선부터 집었습니다. 흩어져 있던 조각들이 나중에 하나로 합쳐지는 방식이었죠. 오늘 마지막 알고리즘은 정반대로 갑니다. 정점 하나에서 시작해 나무를 키워 나가는 방식이에요.

프림(Prim)입니다. 시작 정점 하나를 덩어리로 삼고, 그 덩어리 바깥으로 건너가는 간선 중 가장 싼 것을 골라 흡수합니다. 새 정점이 들어오면 그 정점의 간선들이 새 후보로 추가되고요. 이걸 정점 V개가 다 들어올 때까지 반복하면 끝납니다.

 프림 — 덩어리 바깥으로 건너가는 가장 싼 간선을 계속 흡수한다

   [0]                     후보:  0-1 (1)   0-3 (1)   0-2 (3)
    │  가장 싼 1 을 흡수
    ▼
   [0 1]                   후보:  0-3 (1)   1-2 (1)   0-2 (3)
    │  가장 싼 1 을 흡수
    ▼
   [0 1 2]                 후보:  0-3 (1)   2-3 (1)
    │  가장 싼 1 을 흡수
    ▼
   [0 1 2 3]               정점 4 개가 다 들어왔다 — 끝

   매 단계의 덩어리가 곧 "컷의 한쪽" 이다
   → 프림은 컷 성질을 글자 그대로 구현한 알고리즘이다

프림이 컷 성질을 쓰는 방식이 크루스칼보다 직접적이라는 게 보이시나요? 지금까지 뭉친 덩어리와 나머지, 그게 매 순간의 경계입니다. 그 경계를 건너는 가장 싼 간선을 집으니 컷 성질이 그대로 적용돼요.

그런데 "지금 후보 중 가장 싼 것"을 어떻게 빠르게 꺼낼까요. 이 질문, 우리 이미 여러 번 답했습니다. C-2에서 배열로 직접 짜 본 힙이죠.

def prim(num_vertices, adj_list, start=0):
    visited = set()
    total = 0
    selected = []
    heap = [(0, start, None)]           # (간선 가중치, 도착 정점, 출발 정점)

    while heap and len(visited) < num_vertices:
        weight, node, parent = heapq.heappop(heap)      # 가장 싼 간선을 O(log V)에
        if node in visited:
            continue                    # 게으른 삭제: 이미 덩어리에 들어온 정점
        visited.add(node)
        if parent is not None:          # 시작 정점만 들어온 간선이 없다
            total += weight
            selected.append((parent, node, weight))
        for nxt, w in adj_list.get(node, []):
            if nxt not in visited:      # 덩어리 바깥으로 건너가는 간선만 후보로
                heapq.heappush(heap, (w, nxt, node))
    return total, selected

F-1의 dijkstra_heap을 옆에 놓고 보면 골격이 거의 겹칩니다. 힙에서 꺼내고, 이미 처리한 정점이면 건너뛰고, 이웃을 힙에 넣고. heapq.heappop / heapq.heappush가 도는 모양이 판박이예요.

다익스트라와 갈리는 단 한 줄

그런데 최단 경로와 MST는 전혀 다른 답을 내는 문제잖아요. 코드가 이렇게 닮았는데 어떻게 다른 결과가 나올까요? 차이는 힙에 넣는 값의 의미 하나입니다.

 다익스트라와 프림 — 힙에 무엇을 넣느냐가 전부를 가른다

   다익스트라   heappush(heap, (current_dist + weight, nxt))
                시작점에서 그 정점까지의 "누적 거리"
                → 누적하니까 경로가 나온다

   프림         heappush(heap, (w, nxt, node))
                덩어리에서 그 정점으로 건너가는 "간선 하나의 값"
                → 누적하지 않으니 뼈대가 나온다

다익스트라는 current_dist + weight로 더합니다. 시작점에서부터 걸어온 거리를 계속 누적하죠. 프림은 그냥 w, 간선 하나의 값만 넣어요. 누적하지 않습니다.

이 한 줄이 최단 경로와 MST를 가릅니다. 누적하면 "시작점에서 가장 가까운 정점"이 나오고, 누적하지 않으면 "덩어리에 가장 싸게 붙는 정점"이 나와요. 알고리즘 두 개를 외우는 게 아니라, 같은 골격에 넣는 값을 바꾼 것으로 보시면 기억이 훨씬 오래갑니다.

if node in visited: continue도 다익스트라에서 본 그 관용구입니다. 게으른 삭제(lazy deletion)죠. 어떤 정점으로 가는 간선 후보가 힙에 여러 개 쌓여 있는데, heapq에는 특정 원소만 골라 지우는 기능이 없어요. 그래서 낡은 후보를 그대로 두고 꺼내는 순간에 걸러 냅니다. 이미 덩어리에 들어온 정점이면 그냥 건너뛰는 거예요.

총합은 같은데 간선은 다르다

이제 두 알고리즘을 같은 그래프에 돌려 비교해 봅시다. Step 7의 정사각형 그래프예요.

크루스칼: 3 [(0, 1, 1), (1, 2, 1), (2, 3, 1)]
프림:     3 [(0, 1, 1), (1, 2, 1), (0, 3, 1)]
총 가중치가 같은가: True
고른 간선이 같은가: False

총합은 3으로 똑같은데 고른 간선이 다릅니다. 크루스칼은 2-3을 집었고 프림은 0-3을 집었어요.

이유는 단순합니다. 가중치 1짜리 간선이 네 개나 있어서 어느 것을 먼저 보느냐가 갈렸기 때문이에요. 크루스칼은 정렬된 목록 순서대로 봤고, 프림은 덩어리에 붙는 순서대로 봤습니다.

⚠️ 여기서 정확히 말해야 할 게 있습니다. "MST는 유일하다"고 외우면 틀립니다. 정확한 명제는 이거예요. 간선 가중치가 전부 다르면 MST는 유일하고, 같은 값이 섞여 있으면 MST가 여러 개일 수 있습니다. 다만 어느 MST를 찾든 총 가중치는 반드시 같아요. 여러 개인 것은 구성이지 비용이 아닙니다.

무작위로 만든 연결 그래프 여러 개에 두 알고리즘을 돌려 보면, 고른 간선은 종종 갈리지만 총 가중치는 언제나 일치합니다. 둘 다 컷 성질 위에 서 있으니 당연한 결과예요.

이 성질은 코딩테스트에서 실용적인 의미도 있습니다. MST 문제의 답으로 보통 총 비용을 요구하지 간선 목록을 요구하진 않아요. 답이 유일하지 않은 걸 출제자도 알기 때문입니다.

무엇을 고르나

복잡도부터 짚을게요. log E와 log V가 달라 보이지만, E ≤ V²이므로 log E ≤ 2 log V입니다. 점근적으로는 사실상 같아요. 그러니 이 표를 "프림이 더 빠르다"로 읽으면 안 됩니다.

실질적인 차이는 정렬 비용이 지배하느냐입니다. 크루스칼은 간선 E개를 전부 정렬하는 게 비용의 전부라 간선이 적을수록 유리해요. 프림은 정점을 하나씩 흡수하니 간선이 아무리 많아도 정점 수에만 로그가 붙습니다.

하지만 실전에서 진짜 갈림길은 입력이 어떤 모양으로 들어오느냐예요. 간선 목록으로 주어지면 크루스칼이 그대로 먹고, 인접 리스트로 주어지면 프림이 그대로 먹습니다. 형태를 바꾸는 데 드는 O(E)가 아까워서가 아니라, 코드가 짧아져 실수가 줄기 때문입니다.

🌟 코딩테스트 기본값은 크루스칼입니다. MST 문제는 [(도시A, 도시B, 비용), ...] 형태로 입력이 주어지는 경우가 압도적으로 많거든요. 유니온 파인드만 있으면 코드가 열 줄 안쪽으로 끝납니다. 프림은 인접 리스트가 이미 만들어져 있거나 간선이 유난히 빽빽할 때 꺼내세요.

마지막으로 두 트랙을 정리하고 갈게요. 위상 정렬은 graphlib이라는 내장이 있었지만, MST는 파이썬 표준 라이브러리에 없습니다. 그래프 알고리즘을 본격적으로 담은 외부 패키지(NetworkX 등)에는 있지만 코딩테스트 환경에서는 쓸 수 없어요. 그러니 MST만큼은 직접 구현이 곧 실전입니다. 오늘 짠 열 줄짜리 크루스칼을 그대로 외워 두시면 됩니다.

💡 한 줄 정리

프림은 정점 하나에서 시작해 덩어리 바깥으로 건너가는 가장 싼 간선을 힙에서 꺼내 흡수하며 나무를 키우고, 이는 컷 성질의 직접적인 구현이다. 다익스트라와 골격이 같고 힙에 누적 거리 대신 간선 하나의 값을 넣는 한 줄만 다르다. 크루스칼과 프림은 고른 간선이 갈릴 수 있지만 총 가중치는 반드시 같으며, MST는 가중치가 전부 다를 때만 유일하다. 시간 O(E log V)·공간 O(V)이고, MST는 표준 라이브러리에 없어 직접 구현이 실전이다.

마무리

오늘 우리는 그래프에 세 가지 질문을 던졌습니다. "이 둘이 같은 무리인가", "어떤 순서로 처리해야 하나", "전부 잇는 데 드는 최소 비용은"이요. 지난 시간(F-1)의 질문이 줄곧 "얼마나 먼가"였던 것과 비교하면 결이 완전히 달랐죠.

거리를 재는 눈에서 집합과 순서를 보는 눈으로 옮겨 온 하루였습니다. 같은 그래프인데 무엇을 묻느냐에 따라 완전히 다른 알고리즘이 필요하다는 것, 그리고 그 알고리즘들이 전부 우리가 이미 아는 재료로 만들어졌다는 것. 유니온 파인드는 트리를, 위상 정렬은 BFS와 DFS를, MST는 그리디와 힙과 유니온 파인드를 그대로 가져다 썼습니다.

오늘 배운 핵심 세 가지

💡 하나 — 유니온 파인드는 "같은 무리인가"에 거의 상수 시간으로 답한다. 친구의 친구를 끝까지 따라가지 않고, 대표 하나만 비교하면 됩니다. 경로 압축과 union by rank 두 기법을 얹으면 트리 높이가 log n 안쪽으로 눌리고 분할 상환 비용이 O(α(n))으로 떨어져요. 그리고 union이 돌려주는 True/False 한 값이 사이클 검사기가 되어 크루스칼의 심장으로 쓰였습니다. 자료구조 하나를 잘 설계하면 알고리즘 하나가 열 줄로 끝난다는 걸 보여 준 대목이에요.

💡 둘 — 순서가 있는 문제는 위상 정렬로 줄을 세운다. 선수 과목, 빌드 의존성, 작업 스케줄은 전부 "화살표가 이게 먼저를 뜻하는" 방향 그래프입니다. 카흔은 진입 차수 0부터 꺼내며 BFS의 골격을 그대로 쓰고, DFS판은 후위 순회 뒤 뒤집죠. 답이 여러 개일 수 있고 사이클이면 답이 없습니다. 그리고 위상 순서가 서면 DAG 위의 DP가 열려 최장 경로까지 O(V+E)에 풀렸어요. DP는 채우는 순서가 곧 정확성이라는 걸 번호 순서로 훑는 반례가 숫자로 보여 줬습니다.

💡 셋 — 그리디가 옳으려면 정당성이 필요하고, 정답이 여럿일 수도 있다. MST의 그리디는 컷 성질 위에 서 있고, 그 증명은 E-3의 교환 논법이자 F-1에서 다익스트라를 정당화한 논법과 같은 것이었습니다. 크루스칼과 프림은 서로 다른 간선을 고르지만 총 가중치는 반드시 같아요. "MST는 유일하다"가 틀린 명제이고 "총 가중치는 유일하다"가 맞는 명제라는 것, 이 구분이 알고리즘을 정확히 이해했는지를 가릅니다.

다음 시간 예고

다음 시간(F-3)은 이 과목의 마지막이자, 지금까지 쌓은 모든 것을 실전에서 꺼내 쓰는 법을 다룹니다.

첫째, 문제 유형을 키워드로 분별하는 법입니다. 지문에 "사이클이 생기지 않게"가 보이면 유니온 파인드, "순서"나 "선행 조건"이 보이면 위상 정렬, "전부 잇는 최소 비용"이면 MST예요. F-1에서 최단 경로 세 알고리즘을 고르는 판단표를 만들었듯, 이번엔 오늘까지 배운 그래프 알고리즘 전체를 아우르는 분별표를 세웁니다. 실전에서 시간을 잡아먹는 건 구현이 아니라 "무엇을 꺼낼지 정하는 3분"이거든요.

둘째, 입출력 최적화입니다. 알고리즘은 맞는데 시간 초과가 나는 경우가 있어요. 파이썬 input()이 느려서입니다. sys.stdin.readline으로 바꾸는 한 줄이 통과와 실패를 가르는 상황을 직접 보여 드릴게요.

셋째, 시간 배분과 자주 틀리는 함정입니다. 문제 세 개에 두 시간이 주어졌을 때 어떻게 나눌지, 어떤 반례가 채점기에서 사람들을 무너뜨리는지를 정리합니다. 오늘 본 마름모 그래프나 번호 순서 훑기 같은 함정이 실전에서 어떤 얼굴로 나타나는지도요.

과제

[기초] 몇 개의 무리로 나뉘어 있나

사람 n명이 있고(번호 0부터 n-1), 친구 관계가 [(a, b), ...] 목록으로 주어집니다. 친구의 친구도 같은 무리로 칩니다. 이때 무리가 모두 몇 개인지 반환하는 함수 count_groups(n, friendships)를 작성하세요. 친구가 한 명도 없는 사람은 혼자서 하나의 무리입니다.

예를 들어 count_groups(5, [(0, 1), (1, 2), (3, 4)])는 2입니다. {0, 1, 2}가 한 무리, {3, 4}가 다른 무리니까요. count_groups(4, [])는 아무도 이어져 있지 않으니 4고요.

풀고 나서 한 가지를 더 해 보세요. 이 문제는 E-2에서 BFS로 짠 count_components로도 똑같이 풀립니다. 두 풀이의 시간·공간 복잡도를 나란히 적고, 어떤 상황에서 어느 쪽이 유리한지 한 문단으로 정리해 보세요. 특히 "관계가 하나씩 실시간으로 추가되면서 그때그때 무리 개수를 물어 온다면" 어느 쪽이 맞는지 생각해 보시면 오늘 배운 자료구조의 진가가 보입니다.

예상 시간 25분 · 난이도 하 · 힌트 — 처음엔 무리가 n개입니다. 간선 하나가 서로 다른 두 무리를 이을 때마다 개수가 하나씩 줄어들어요.

[응용] 들을 수 있는 순서를 내놓아라

과목 n개가 있고(번호 0부터 n-1), 선수 관계가 [(먼저, 나중), ...] 목록으로 주어집니다. (0, 1)은 "0번을 들어야 1번을 들을 수 있다"는 뜻이에요. 모든 과목을 들을 수 있는 수강 순서를 리스트로 반환하는 함수 course_order(n, prerequisites)를 작성하세요. 어떤 순서로도 전부 들을 수 없으면 빈 리스트를 반환합니다.

예를 들어 course_order(4, [(0, 1), (0, 2), (1, 3), (2, 3)])은 [0, 1, 2, 3]이나 [0, 2, 1, 3]처럼 조건을 만족하는 순서 아무거나면 됩니다. 반면 course_order(2, [(0, 1), (1, 0)])은 두 과목이 서로를 선수로 요구하니 []예요.

주의할 점 두 가지를 미리 알려 드릴게요. 첫째, 선수 관계에 한 번도 등장하지 않는 과목도 결과에 들어가야 합니다. 아무 조건 없이 들을 수 있는 과목이니까요. 둘째, 간선 목록을 인접 리스트로 바꾸는 것부터가 문제의 절반입니다. 시간·공간 복잡도를 빅오로 함께 적으세요.

예상 시간 30분 · 난이도 중 · 힌트 — 진입 차수를 세는 것과 인접 리스트를 만드는 것을 같은 반복문에서 한 번에 처리하면 코드가 짧아집니다.

[심화] 이미 깔린 도로가 있다면

마을 n개를 전부 잇는 도로망을 만들려고 합니다. 놓을 수 있는 도로 후보가 [(마을A, 마을B, 비용), ...]로 주어지는데, 그중 일부는 이미 건설이 끝나 비용이 들지 않습니다. 이미 건설된 도로는 built = [(마을A, 마을B), ...] 목록으로 따로 주어져요. 모든 마을을 잇는 데 추가로 드는 최소 비용을 반환하는 함수 remaining_cost(n, roads, built)를 작성하세요. 어떻게 해도 전부 이을 수 없으면 -1을 반환합니다.

예를 들어 n = 4, roads = [(0, 1, 5), (1, 2, 3), (2, 3, 4), (0, 3, 10)]이고 built = [(0, 1)]이라면, 0-1은 이미 있으니 3과 4짜리만 더 놓으면 됩니다. 답은 7이에요.

핵심은 오늘 만든 크루스칼을 거의 그대로 쓰되, 시작 상태만 바꾸는 것입니다. "이미 이어져 있다"를 유니온 파인드로 어떻게 표현할지 생각해 보세요. 비용 0짜리 간선으로 취급해도 되고, 정렬 전에 미리 처리해도 됩니다. 두 방법이 같은 답을 내는지도 확인해 보시면 좋아요. 도로를 하나도 더 못 놓는 경우와 애초에 이을 방법이 없는 경우를 구분하는 것도 잊지 마세요. 시간·공간 복잡도를 빅오로 적으세요.

예상 시간 40분 · 난이도 상 · 힌트 — 크루스칼을 돌리기 전에 built의 도로들로 먼저 union을 불러 두면, 그 뒤는 평소와 똑같습니다. 연결 판정은 남은 집합 개수나 선택된 간선 수로 하시면 돼요.

생각해볼 주제

1. 첫 호출은 비싸고 그다음부터 싸다면, 그건 빠른 건가

경로 압축은 첫 find 호출에서 아무 이득이 없습니다. 오히려 길을 새로 잇느라 일을 더 하죠. 대신 두 번째 호출부터 극적으로 싸집니다. 그래서 한 번의 최악 비용이 아니라 여러 번의 평균으로 따지는 분할 상환 관점이 필요했어요. 이런 비용 구조는 자료구조 바깥에도 흔합니다. 여러분이 이미 아는 것 중에서 "미리 비용을 치르고 나중에 회수하는" 구조를 찾아보고, 그런 것들의 성능을 어떤 잣대로 재야 공정한지 정리해 보세요.

2. 정답이 여러 개인데 하나를 강제해야 한다면

위상 정렬의 답은 대개 여러 개이고, 오늘 카흔과 DFS가 실제로 다른 순서를 냈습니다. 그런데 현실에서는 "매번 같은 순서로 빌드돼야 한다"거나 "결과를 캐시에 재사용해야 한다"처럼 답 하나를 못 박아야 하는 상황이 생깁니다. 여러 정답 중 하나를 결정적으로 고르게 만들려면 알고리즘에 무엇을 추가해야 하고, 그 대가로 복잡도는 어떻게 달라질까요. 그렇게 고른 순서가 "더 나은 순서"이기도 한지까지 생각해 보시면 좋습니다.

3. 정답이 여럿인 문제를 어떻게 채점하나

크루스칼과 프림은 서로 다른 간선을 골랐지만 둘 다 맞았습니다. 이런 문제를 채점하거나 테스트할 때 기대 출력과 글자 단위로 비교하는 방식은 통하지 않아요. 그러면 무엇을 검사해야 "이 답이 맞다"고 판정할 수 있을까요. 오늘 배운 MST와 위상 정렬을 예로 들어, 정답의 조건을 어떻게 검사 가능한 형태로 바꿔 쓸 수 있을지 정리해 보세요. 코딩테스트 채점기가 여러분의 답을 어떻게 보고 있는지 짐작해 보는 계기가 될 겁니다.