그래프에서 한 걸음 더 들어가면 트리가 보인다
그래프 문제를 풀다 보면 자주 이런 조건을 만납니다.
"모든 노드가 연결되어 있다."
"사이클이 없다."
"어떤 노드에서 다른 노드로 가는 경로가 하나뿐이다."
이 조건들이 모이면 우리가 다룰 구조는 거의 항상 트리입니다. 트리는 그래프의 특별한 형태입니다. 정점과 간선으로 이루어져 있지만, 아무렇게나 연결된 그래프와 달리 구조가 훨씬 단정합니다. 그래서 트리를 잘 이해하면 부모 찾기, 조직도 분석, 파일 시스템, 족보, 네트워크 연결 비용 같은 문제를 훨씬 쉽게 풀 수 있습니다.
트리의 가장 중요한 특징은 사이클이 없고 연결되어 있다는 점입니다. 노드가 N개인 트리는 항상 간선이 N - 1개입니다. 이 사실은 코딩 테스트에서 꽤 자주 힌트가 됩니다. 입력으로 노드 N개와 간선 N - 1개가 주어지고, 모든 노드가 연결되어 있다면 그 구조는 트리라고 볼 수 있습니다.
트리를 떠올릴 때는 회사 조직도를 생각하면 쉽습니다. 대표가 있고, 그 아래 임원이 있고, 그 아래 팀장이 있으며, 그 아래 팀원이 있습니다. 위아래 관계가 있고, 어떤 사람의 아래에 속한 사람들의 묶음도 하나의 작은 조직처럼 볼 수 있습니다. 이 작은 조직이 바로 서브트리입니다.
트리의 기본 용어를 문제 언어로 바꾸기
트리 문제는 용어가 조금 많습니다. 하지만 용어 자체보다 중요한 것은 이 용어들이 코드에서 무엇으로 표현되는지 이해하는 것입니다.
트리에서 한 노드를 기준으로 위쪽에 있는 노드를 부모라고 합니다. 아래쪽에 직접 연결된 노드를 자식이라고 합니다. 최상단 노드는 루트입니다. 루트에서 어떤 노드까지 내려가는 데 거치는 간선 수를 깊이라고 합니다. 더 이상 자식이 없는 노드는 리프 노드입니다.
예를 들어 다음과 같은 트리가 있다고 해봅시다.
1
/ \
2 3
/ \
4 5 6이 트리에서 1은 루트입니다. 2와 3의 부모는 1입니다. 4와 5의 부모는 2입니다. 4, 5, 6은 자식이 없으므로 리프 노드입니다. 루트 1의 깊이는 0, 2와 3의 깊이는 1, 4, 5, 6의 깊이는 2입니다.
문제에서 "각 노드의 부모를 구하라"라고 하면 parent 배열을 만들면 됩니다. "각 노드의 깊이를 구하라"라고 하면 depth 배열을 만들면 됩니다. "어떤 노드를 루트로 하는 서브트리의 크기를 구하라"라고 하면 subtree_size 배열을 만들면 됩니다.
즉, 트리 문제의 많은 답은 배열에 저장됩니다.
parent = [0] * (n + 1)
depth = [0] * (n + 1)
subtree_size = [0] * (n + 1)처음에는 트리라는 말이 거창하게 느껴질 수 있지만, 실제 풀이에서는 "연결 정보를 리스트로 저장하고, DFS나 BFS로 한 번 훑으면서 필요한 값을 배열에 채운다"가 핵심입니다.
트리는 보통 인접 리스트로 표현한다
트리도 그래프의 한 종류이므로 인접 리스트로 표현하는 방식이 가장 흔합니다. 노드 수가 많을 수 있기 때문에 인접 행렬보다 인접 리스트가 효율적입니다.
다음 입력이 있다고 해봅시다.
6
1 2
1 3
2 4
2 5
3 6이 입력은 노드가 6개이고, 간선이 5개인 트리를 의미합니다. 무방향 트리라면 양쪽으로 모두 연결해주어야 합니다.
n = 6
graph = [[] for _ in range(n + 1)]
edges = [
(1, 2),
(1, 3),
(2, 4),
(2, 5),
(3, 6),
]
for a, b in edges:
graph[a].append(b)
graph[b].append(a)이제 graph[1]에는 2, 3이 들어 있고, graph[2]에는 1, 4, 5가 들어 있습니다. 여기서 조심할 점은 트리 입력이 대부분 무방향 간선으로 주어진다는 것입니다. 부모와 자식이 처음부터 정해져 있지 않습니다.
따라서 루트를 하나 정한 뒤 탐색하면서 부모와 자식 관계를 만들어야 합니다. 보통 문제에서 루트를 지정해주거나, 지정이 없다면 1번 노드를 루트로 잡는 경우가 많습니다.
DFS로 부모와 깊이 구하기
트리에서 가장 기본적인 작업은 루트에서 출발해 모든 노드를 방문하면서 부모와 깊이를 기록하는 것입니다.
무방향 트리에서는 자식으로 내려가다가 다시 부모로 돌아가는 간선도 보입니다. 따라서 DFS를 할 때 "다음 노드가 부모라면 건너뛰기" 처리가 필요합니다.
def dfs(node, par):
parent[node] = par
for nxt in graph[node]:
if nxt == par:
continue
depth[nxt] = depth[node] + 1
dfs(nxt, node)
n = 6
graph = [[] for _ in range(n + 1)]
parent = [0] * (n + 1)
depth = [0] * (n + 1)
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
dfs(1, 0)이 코드가 끝나면 parent[4]는 2, depth[4]는 2가 됩니다. parent[1]은 루트이므로 0으로 둡니다.
물론 BFS로도 부모와 깊이를 구할 수 있습니다. 하지만 트리의 서브트리 크기, 리프 노드 계산, 후위 처리처럼 "자식들을 먼저 처리한 뒤 부모를 계산해야 하는 문제"에서는 DFS가 특히 자연스럽습니다.
재귀 DFS를 사용할 때는 입력 크기를 확인해야 합니다. 노드 수가 매우 크면 파이썬에서는 재귀 깊이 제한에 걸릴 수 있습니다. 그럴 때는 sys.setrecursionlimit()을 늘리거나, 반복문 기반 DFS를 고려해야 합니다.
import sys
sys.setrecursionlimit(10**6)코딩 테스트에서는 이 한 줄 때문에 맞고 틀리는 경우가 실제로 있습니다. 트리 DFS 문제에서 노드 수가 10만 이상이라면 재귀 깊이를 반드시 의식하세요.
리프 노드 계산: 자식이 없다는 것을 어떻게 판단할까
리프 노드는 자식이 없는 노드입니다. 하지만 무방향 인접 리스트만 보고 단순히 len(graph[node]) == 1이라고 판단하면 항상 맞지는 않습니다. 루트가 리프가 될 수 있는 특수한 경우가 있기 때문입니다.
노드가 여러 개 있는 트리에서는 루트가 아닌 노드 중 연결된 간선이 하나뿐이면 리프입니다. 부모 하나만 있고 자식이 없다는 뜻이기 때문입니다. 하지만 노드가 1개뿐인 트리에서는 루트 자신이 리프입니다.
더 안전한 방식은 DFS 중 실제 자식 수를 세는 것입니다.
def count_leaf(node, par):
child_count = 0
leaf_count = 0
for nxt in graph[node]:
if nxt == par:
continue
child_count += 1
leaf_count += count_leaf(nxt, node)
if child_count == 0:
return 1
return leaf_count이 함수는 현재 노드에서 부모로 돌아가는 간선을 제외한 뒤, 실제 자식이 몇 개인지 셉니다. 자식이 하나도 없다면 리프이므로 1을 반환합니다. 자식이 있다면 자식들의 리프 개수를 모두 더해서 반환합니다.
이런 식의 DFS는 트리 문제에서 매우 자주 등장합니다. "내 자식들이 계산한 값을 모아서 내가 답을 만든다"는 흐름입니다. 이 흐름은 동적 계획법과도 닮아 있습니다. 트리 위에서 하는 DP를 흔히 트리 DP라고 부릅니다. 지금은 이름보다 감각이 중요합니다. 아래에서 올라오는 값을 부모가 모은다는 느낌을 기억하면 됩니다.
서브트리 크기 구하기
서브트리는 어떤 노드와 그 아래에 있는 모든 노드를 포함한 부분 트리입니다. 예를 들어 앞의 예시에서 2를 루트로 하는 서브트리에는 2, 4, 5가 포함됩니다. 크기는 3입니다.
서브트리 크기도 DFS로 쉽게 구할 수 있습니다.
def dfs_size(node, par):
subtree_size[node] = 1
for nxt in graph[node]:
if nxt == par:
continue
dfs_size(nxt, node)
subtree_size[node] += subtree_size[nxt]핵심은 subtree_size[node] = 1에서 시작한다는 점입니다. 자기 자신을 먼저 포함합니다. 그다음 자식들의 서브트리 크기를 모두 더합니다.
이 패턴은 문제에 따라 다양한 모습으로 변합니다.
어떤 노드를 제거했을 때 나뉘는 컴포넌트 크기 구하기
각 직원 아래에 있는 부하 직원 수 구하기
루트가 바뀌어도 특정 방향의 노드 개수 계산하기
트리에서 특정 조건을 만족하는 노드 개수 누적하기
문장을 다르게 포장해도 결국 코드는 "자식에게 갔다가 돌아오면서 값을 더한다"입니다.
유니온 파인드: 연결 여부를 빠르게 묻는 자료구조
이제 트리에서 잠시 벗어나 집합 이야기를 해보겠습니다. 코딩 테스트에서는 다음과 같은 질문이 자주 나옵니다.
"두 사람이 같은 팀인가?"
"두 도시가 이미 연결되어 있는가?"
"이 간선을 추가하면 사이클이 생기는가?"
"여러 원소를 계속 합치면서 마지막에 몇 개의 그룹이 남는가?"
이런 문제를 매번 DFS나 BFS로 확인하면 너무 느릴 수 있습니다. 연결 관계가 계속 바뀌는 상황에서는 유니온 파인드가 강력합니다.
유니온 파인드는 서로소 집합 자료구조라고도 합니다. 여기서 서로소란 "겹치지 않는다"는 뜻입니다. 처음에는 모든 원소가 각자 자기 집합에 속해 있습니다. 그러다가 union 연산으로 두 집합을 합칩니다. find 연산으로 어떤 원소가 속한 집합의 대표를 찾습니다.
가장 기본적인 형태는 다음과 같습니다.
parent = [i for i in range(n + 1)]
def find(x):
if parent[x] == x:
return x
return find(parent[x])
def union(a, b):
root_a = find(a)
root_b = find(b)
if root_a == root_b:
return False
parent[root_b] = root_a
return True처음에는 parent[i] = i입니다. 자기 자신이 대표라는 뜻입니다. union(1, 2)를 하면 1과 2의 대표를 찾고, 한쪽 대표가 다른 쪽 대표를 가리키게 만듭니다. 그러면 두 원소는 같은 집합이 됩니다.
union 함수가 False를 반환하는 경우도 중요합니다. 두 원소의 대표가 이미 같다면, 두 원소는 이미 같은 집합에 있습니다. 그래프 문제에서는 이때 간선을 추가하면 사이클이 생긴다고 볼 수 있습니다.
경로 압축: find를 빠르게 만드는 핵심
기본 유니온 파인드는 최악의 경우 부모 포인터가 긴 사슬처럼 이어질 수 있습니다.
1 <- 2 <- 3 <- 4 <- 5이 상태에서 find(5)를 하면 5에서 4, 3, 2, 1까지 계속 올라가야 합니다. 원소 수가 많고 연산도 많으면 느려집니다.
그래서 사용하는 최적화가 경로 압축입니다. 대표를 찾으러 올라가는 김에, 지나간 노드들이 바로 대표를 가리키도록 바꿔버리는 방식입니다.
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]이 한 줄이 핵심입니다.
parent[x] = find(parent[x])처음에는 여러 단계를 거쳐 대표를 찾더라도, 한 번 찾고 나면 다음부터는 거의 바로 대표를 찾을 수 있습니다. 그래서 유니온 파인드 문제에서는 find를 거의 항상 경로 압축 형태로 작성하는 것이 좋습니다.
랭크 기반 합치기: 트리를 납작하게 유지하기
경로 압축만으로도 대부분의 코딩 테스트 문제는 충분히 통과합니다. 하지만 유니온 파인드의 정석 구현을 익히려면 랭크 기반 합치기도 알아두는 것이 좋습니다.
유니온 파인드 내부에서도 부모 관계가 생기기 때문에 작은 트리들이 만들어집니다. 이때 아무렇게나 합치면 한쪽으로 길게 늘어질 수 있습니다. 랭크 기반 합치기는 높이가 낮은 트리를 높이가 높은 트리 아래에 붙이는 전략입니다.
여기서 랭크는 정확한 높이라기보다는 "대략적인 높이 정보"라고 이해하면 됩니다.
parent = [i for i in range(n + 1)]
rank = [0] * (n + 1)
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(a, b):
root_a = find(a)
root_b = find(b)
if root_a == root_b:
return False
if rank[root_a] < rank[root_b]:
parent[root_a] = root_b
elif rank[root_a] > rank[root_b]:
parent[root_b] = root_a
else:
parent[root_b] = root_a
rank[root_a] += 1
return True두 대표의 랭크가 다르면 낮은 쪽을 높은 쪽 아래에 붙입니다. 랭크가 같다면 한쪽을 다른 쪽 아래에 붙이고, 대표가 된 쪽의 랭크를 1 증가시킵니다.
실전에서는 랭크 대신 집합의 크기를 기준으로 합치기도 합니다. 작은 집합을 큰 집합 아래에 붙이는 방식입니다.
size = [1] * (n + 1)
def union(a, b):
root_a = find(a)
root_b = find(b)
if root_a == root_b:
return False
if size[root_a] < size[root_b]:
root_a, root_b = root_b, root_a
parent[root_b] = root_a
size[root_a] += size[root_b]
return True이 방식은 "현재 집합의 크기를 알아야 하는 문제"에서도 유용합니다. 예를 들어 친구 네트워크에서 두 사람을 연결할 때마다 그 네트워크의 사람 수를 출력하는 문제라면 size 배열을 함께 관리하면 됩니다.
유니온 파인드로 사이클 판별하기
유니온 파인드의 대표적인 활용은 무방향 그래프에서 사이클을 판별하는 것입니다.
간선을 하나씩 보면서 두 노드가 이미 같은 집합인지 확인합니다. 이미 같은 집합이라면, 두 노드 사이에는 기존 경로가 있다는 뜻입니다. 여기에 간선을 하나 더 추가하면 사이클이 생깁니다.
def has_cycle(n, edges):
parent = [i for i in range(n + 1)]
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(a, b):
root_a = find(a)
root_b = find(b)
if root_a == root_b:
return False
parent[root_b] = root_a
return True
for a, b in edges:
if not union(a, b):
return True
return False이 코드는 크루스칼 알고리즘에서도 그대로 사용됩니다. 크루스칼 알고리즘의 핵심이 바로 "사이클을 만들지 않는 가장 싼 간선부터 선택하기"이기 때문입니다.
최소 신장 트리: 모든 노드를 가장 싸게 연결하기
이제 이번 장의 마지막 큰 주제인 최소 신장 트리로 가봅시다.
먼저 신장 트리부터 이해해야 합니다. 어떤 그래프에서 모든 노드를 포함하면서 사이클이 없는 연결 구조를 만들면 그것이 신장 트리입니다. 노드가 N개라면 신장 트리의 간선 수는 반드시 N - 1개입니다.
여기에 비용 조건이 붙습니다. 가능한 여러 신장 트리 중 간선 비용의 합이 가장 작은 트리를 최소 신장 트리, 줄여서 MST라고 부릅니다.
상황을 하나 상상해봅시다. 여러 도시가 있고, 도시 사이에 도로를 놓을 수 있습니다. 각 도로마다 건설 비용이 다릅니다. 모든 도시가 서로 오갈 수 있게 연결해야 하지만, 비용은 최소로 하고 싶습니다. 이때 필요한 것이 최소 신장 트리입니다.
중요한 점은 "모든 도시 사이를 직접 연결할 필요는 없다"는 것입니다. 모든 도시가 간접적으로라도 연결되면 됩니다. A에서 C로 직접 도로가 없어도 A -> B -> C로 갈 수 있다면 연결된 것입니다. 따라서 간선은 정확히 N - 1개만 선택하면 됩니다.
크루스칼 알고리즘의 생각법
최소 신장 트리를 구하는 대표 알고리즘이 크루스칼 알고리즘입니다. 생각은 아주 단순합니다.
가장 싼 간선부터 보자.
단, 사이클이 생기면 고르지 말자.
간선이 N - 1개가 될 때까지 반복하자.
이 전략은 그리디 알고리즘입니다. 매 순간 가장 비용이 낮은 간선을 선택하기 때문입니다. 하지만 무조건 고르는 것은 아닙니다. 사이클을 만들면 선택하지 않습니다. 사이클이 생기면 어떤 간선 하나는 불필요해지기 때문입니다.
크루스칼 알고리즘의 절차는 다음과 같습니다.
모든 간선을 비용 기준으로 오름차순 정렬한다.
간선을 하나씩 확인하면서 두 노드가 이미 연결되어 있는지 유니온 파인드로 검사한다.
연결되어 있지 않다면 그 간선을 선택하고 두 집합을 합친다.
선택한 간선 수가
N - 1개가 되면 종료한다.
예를 들어 간선 정보가 다음과 같다고 해봅시다.
노드 수: 4
간선:
1 2 3
1 3 2
2 3 1
2 4 5
3 4 4각 줄은 a b cost를 의미합니다. 가장 싼 간선은 2-3 비용 1입니다. 선택합니다. 다음은 1-3 비용 2입니다. 아직 1과 3은 연결되어 있지 않으므로 선택합니다. 다음은 1-2 비용 3입니다. 하지만 1과 2는 이미 1-3-2 경로로 연결되어 있습니다. 이 간선을 선택하면 사이클이 생기므로 버립니다. 다음은 3-4 비용 4입니다. 선택합니다.
선택한 간선은 2-3, 1-3, 3-4입니다. 노드가 4개이므로 간선 3개를 골랐고, 모든 노드가 연결되었습니다. 총 비용은 1 + 2 + 4 = 7입니다.
크루스칼 알고리즘 구현하기
이제 코드로 구현해봅시다.
def kruskal(n, edges):
# edges: (cost, a, b)
edges.sort()
parent = [i for i in range(n + 1)]
rank = [0] * (n + 1)
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(a, b):
root_a = find(a)
root_b = find(b)
if root_a == root_b:
return False
if rank[root_a] < rank[root_b]:
parent[root_a] = root_b
elif rank[root_a] > rank[root_b]:
parent[root_b] = root_a
else:
parent[root_b] = root_a
rank[root_a] += 1
return True
total_cost = 0
selected = 0
for cost, a, b in edges:
if union(a, b):
total_cost += cost
selected += 1
if selected == n - 1:
break
if selected != n - 1:
return None
return total_costedges를 (cost, a, b) 형태로 저장하면 edges.sort()만으로 비용 기준 오름차순 정렬이 됩니다. 파이썬의 튜플 정렬은 첫 번째 원소부터 비교하기 때문입니다.
마지막의 if selected != n - 1도 중요합니다. 모든 간선을 확인했는데도 N - 1개를 선택하지 못했다면, 그래프가 애초에 모두 연결될 수 없는 상태입니다. 즉, 최소 신장 트리가 존재하지 않습니다. 문제에 따라 이 경우 -1을 출력하라고 하거나, 따로 예외 처리를 요구할 수 있습니다.
입력까지 포함한 전형적인 코드는 다음과 같습니다.
import sys
input = sys.stdin.readline
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(a, b):
root_a = find(a)
root_b = find(b)
if root_a == root_b:
return False
if rank[root_a] < rank[root_b]:
parent[root_a] = root_b
elif rank[root_a] > rank[root_b]:
parent[root_b] = root_a
else:
parent[root_b] = root_a
rank[root_a] += 1
return True
n, m = map(int, input().split())
edges = []
for _ in range(m):
a, b, cost = map(int, input().split())
edges.append((cost, a, b))
edges.sort()
parent = [i for i in range(n + 1)]
rank = [0] * (n + 1)
answer = 0
count = 0
for cost, a, b in edges:
if union(a, b):
answer += cost
count += 1
if count == n - 1:
break
if count == n - 1:
print(answer)
else:
print(-1)이 코드는 최소 신장 트리 문제의 기본 뼈대입니다. 문제 조건이 조금 달라져도 대부분 이 구조에서 시작하면 됩니다.
크루스칼 알고리즘의 시간 복잡도
크루스칼 알고리즘에서 가장 큰 비용은 간선 정렬입니다. 간선 수를 E라고 하면 정렬 비용은 O(E log E)입니다.
유니온 파인드 연산은 경로 압축과 랭크 기반 합치기를 사용하면 매우 빠르게 동작합니다. 실전에서는 거의 상수 시간처럼 생각해도 됩니다. 따라서 전체 시간 복잡도는 보통 O(E log E)라고 말합니다.
이 복잡도 감각은 문제 선택에도 도움이 됩니다. 간선이 20만 개, 50만 개 정도라면 파이썬에서도 정렬 기반 크루스칼을 충분히 고려할 수 있습니다. 다만 간선이 너무 많아 완전 그래프에 가까운 경우에는 입력 크기 자체가 커지므로 문제 조건을 꼼꼼히 봐야 합니다.
공간 복잡도는 간선 목록을 저장하는 데 O(E), 유니온 파인드 배열에 O(V)가 필요합니다. 여기서 V는 노드 수입니다.
최소 신장 트리 문제를 알아보는 신호
문제를 읽을 때 다음 표현이 보이면 최소 신장 트리를 의심해볼 수 있습니다.
모든 지점, 도시, 컴퓨터, 섬을 연결해야 한다.
연결 비용, 설치 비용, 유지 비용의 합을 최소화해야 한다.
사이클이 필요 없고 연결만 되면 된다.
이미 가능한 연결 후보들이 비용과 함께 주어진다.
예를 들어 "모든 섬을 다리로 연결하는 최소 비용"이라는 문제는 거의 대놓고 MST입니다. "모든 컴퓨터를 네트워크로 연결하되 비용을 최소로 하라"도 마찬가지입니다.
반대로 최단 경로 문제와 헷갈리면 안 됩니다. 최단 경로는 특정 출발점에서 특정 도착점까지의 비용을 최소화하는 문제입니다. 최소 신장 트리는 모든 노드를 하나의 연결 구조로 묶는 비용을 최소화하는 문제입니다.
즉, "A에서 B까지 가장 싸게 가기"는 최단 경로입니다. "모든 도시를 연결하는 도로망을 가장 싸게 만들기"는 최소 신장 트리입니다.
트리, 유니온 파인드, 크루스칼은 서로 이어진다
처음 보면 이번 장의 주제들이 따로 떨어져 있는 것처럼 느껴질 수 있습니다. 트리는 계층 구조이고, 유니온 파인드는 집합 자료구조이고, 크루스칼은 최소 신장 트리 알고리즘입니다. 하지만 세 주제는 생각보다 단단히 연결되어 있습니다.
트리는 사이클 없는 연결 그래프입니다. 유니온 파인드는 간선을 추가할 때 사이클이 생기는지 빠르게 판단합니다. 크루스칼 알고리즘은 유니온 파인드로 사이클을 피하면서 가장 싼 간선들을 골라 결국 트리를 만듭니다. 즉, 크루스칼의 결과가 바로 최소 비용의 트리입니다.
이 연결 관계를 이해하면 암기할 것이 줄어듭니다. 크루스칼을 외우는 대신 이렇게 생각하면 됩니다.
"가장 싼 간선부터 고르되, 트리여야 하니까 사이클은 만들지 않는다. 사이클 여부는 유니온 파인드로 확인한다."
이 한 문장이 크루스칼 알고리즘의 전부에 가깝습니다.
실전에서 자주 하는 실수들
트리와 유니온 파인드 문제는 코드가 짧아 보이지만, 작은 실수로 오답이 나기 쉽습니다.
첫 번째 실수는 무방향 트리에서 부모로 되돌아가는 간선을 처리하지 않는 것입니다. DFS에서 if nxt == par: continue를 빠뜨리면 무한 재귀가 발생할 수 있습니다.
두 번째 실수는 유니온 파인드에서 find를 하지 않고 단순히 parent[a]와 parent[b]를 비교하는 것입니다. parent[x]는 당장 한 단계 위의 부모일 뿐, 집합의 대표가 아닐 수 있습니다. 연결 여부를 판단할 때는 반드시 find(a) == find(b)를 사용해야 합니다.
세 번째 실수는 크루스칼에서 간선을 비용 기준으로 정렬하지 않는 것입니다. 입력이 이미 정렬되어 있다는 보장이 없다면 반드시 정렬해야 합니다.
네 번째 실수는 선택한 간선 수를 확인하지 않는 것입니다. 그래프가 연결되어 있지 않으면 모든 노드를 연결할 수 없습니다. 이때도 비용을 출력해버리면 틀립니다. 선택한 간선 수가 N - 1개인지 확인해야 합니다.
마지막 실수는 0번 인덱스와 1번 인덱스를 혼동하는 것입니다. 문제에서 노드 번호가 1부터 시작하면 배열 크기를 n + 1로 만드는 편이 안전합니다. 노드 번호가 0부터 시작하면 n 크기로 만들고 범위를 정확히 맞춰야 합니다.
연습 문제를 풀 때의 접근 순서
이번 장의 주제를 연습할 때는 문제를 읽고 바로 코드부터 쓰지 말고, 먼저 어떤 유형인지 구분하는 습관을 들이면 좋습니다.
트리 문제라면 루트를 정해야 하는지부터 봅니다. 루트가 정해지면 부모, 깊이, 서브트리 크기 중 무엇을 구해야 하는지 생각합니다. 대부분 DFS 한 번으로 필요한 배열을 채울 수 있습니다.
유니온 파인드 문제라면 "합치기"와 "같은 집합인지 확인하기"가 반복되는지 봅니다. 친구 관계, 팀 합치기, 네트워크 연결, 사이클 판별 같은 표현이 나오면 유니온 파인드를 떠올리세요.
최소 신장 트리 문제라면 모든 노드를 연결해야 하는지, 비용의 합을 최소화해야 하는지 확인합니다. 그렇다면 간선을 비용 기준으로 정렬하고, 유니온 파인드로 사이클을 피하면서 선택하면 됩니다.
문제를 많이 풀다 보면 어느 순간 문장만 읽어도 풀이 방향이 보입니다. "모든 섬을 연결", "최소 비용", "다리 후보"가 보이면 머릿속에서 자동으로 edges.sort()와 union()이 떠오르는 식입니다. 이 자동 반응을 만드는 것이 코딩 테스트 준비의 핵심입니다.
이번 장의 핵심 정리
트리는 그래프의 특별한 형태이며, 계층 구조를 표현하는 데 강합니다. 부모, 자식, 깊이, 서브트리 같은 개념은 대부분 배열과 인접 리스트로 구현됩니다. DFS를 사용하면 부모 찾기, 깊이 계산, 리프 노드 계산, 서브트리 크기 계산을 자연스럽게 처리할 수 있습니다.
유니온 파인드는 여러 원소를 집합으로 관리하면서 두 원소가 같은 집합에 속하는지 빠르게 확인하는 자료구조입니다. find는 대표를 찾고, union은 두 집합을 합칩니다. 경로 압축과 랭크 기반 합치기를 사용하면 매우 효율적으로 동작합니다.
최소 신장 트리는 모든 노드를 연결하는 가장 싼 트리입니다. 크루스칼 알고리즘은 간선을 비용 기준으로 정렬한 뒤, 사이클을 만들지 않는 간선만 선택합니다. 사이클 여부는 유니온 파인드로 판단합니다.
이번 장에서 배운 내용은 그래프 문제를 더 깊게 풀기 위한 필수 도구입니다. 트리 DFS로 계층 구조를 분석하고, 유니온 파인드로 연결 관계를 관리하며, 크루스칼로 최소 비용 연결 구조를 만들 수 있다면 코딩 테스트의 그래프 영역에서 한 단계 더 안정적인 풀이를 할 수 있습니다.
이 노트는 보도·비평·교육·연구 목적으로 작성되었습니다. 저작권 문의가 있으시면 에서 알려주세요.