문제 요약
루트가 정해지지 않은 여러 개의 트리, 즉 포레스트가 주어진다.
각 노드는 서로 다른 번호를 가지고 있다.
루트를 정하면 각 노드의 자식 수가 결정되고, 노드 번호와 자식 수의 홀짝 관계에 따라 노드의 종류가 나뉜다.
노드 종류
홀수 노드
노드 번호: 홀수
자식 수: 홀수짝수 노드
노드 번호: 짝수
자식 수: 짝수0은 짝수로 본다.
역홀수 노드
노드 번호: 홀수
자식 수: 짝수역짝수 노드
노드 번호: 짝수
자식 수: 홀수홀수 노드와 짝수 노드로만 구성된 트리를 홀짝 트리라고 한다.
역홀수 노드와 역짝수 노드로만 구성된 트리를 역홀짝 트리라고 한다.
각 트리에서 적절한 노드를 루트로 선택했을 때 다음 두 값을 구해야 한다.
- 홀짝 트리가 될 수 있는 트리의 개수
- 역홀짝 트리가 될 수 있는 트리의 개수
핵심 아이디어
이 문제의 핵심은 무방향 트리에서의 차수와 루트를 정한 후의 자식 수 관계다.
노드의 차수는 해당 노드에 연결된 간선의 개수다.
어떤 노드를 루트로 정하면 다음 관계가 성립한다.
루트 노드
루트 노드에는 부모가 없다.
따라서 루트와 연결된 모든 노드는 자식이 된다.
루트의 자식 수 = 루트의 차수루트가 아닌 노드
루트가 아닌 노드에는 부모가 정확히 하나 존재한다.
연결된 노드 중 하나는 부모이고, 나머지가 자식이다.
자식 수 = 차수 - 1차수 - 1은 원래 차수와 홀짝이 반대다.
차수가 짝수라면 차수 - 1은 홀수
차수가 홀수라면 차수 - 1은 짝수즉, 루트를 정하면 루트 노드만 차수와 자식 수의 홀짝이 같고, 나머지 모든 노드는 차수와 자식 수의 홀짝이 반대가 된다.
번호와 차수의 홀짝 비교
각 노드에 대해 다음 조건을 확인한다.
node_number % 2 == degree % 2조건이 참이라면 노드 번호와 차수의 홀짝이 같은 노드다.
조건이 거짓이라면 노드 번호와 차수의 홀짝이 다른 노드다.
이 분류만으로 해당 트리가 홀짝 트리 또는 역홀짝 트리가 될 수 있는지 판단할 수 있다.
홀짝 트리가 되는 조건
홀짝 트리의 모든 노드는 번호와 자식 수의 홀짝이 같아야 한다.
루트 노드
루트의 자식 수는 차수와 같다.
따라서 루트는 다음 조건을 만족해야 한다.
노드 번호의 홀짝 = 차수의 홀짝루트가 아닌 노드
루트가 아닌 노드의 자식 수는 차수 - 1이다.
자식 수와 차수의 홀짝은 반대이므로, 번호와 자식 수의 홀짝이 같으려면 다음 조건이 필요하다.
노드 번호의 홀짝 != 차수의 홀짝따라서 하나의 트리에서 다음 조건이 성립해야 한다.
번호와 차수의 홀짝이 같은 노드가 정확히 1개그 노드를 루트로 정하면 홀짝 트리가 된다.
역홀짝 트리가 되는 조건
역홀짝 트리의 모든 노드는 번호와 자식 수의 홀짝이 달라야 한다.
루트 노드
루트의 자식 수는 차수와 같다.
따라서 루트는 다음 조건을 만족해야 한다.
노드 번호의 홀짝 != 차수의 홀짝루트가 아닌 노드
루트가 아닌 노드는 자식 수와 차수의 홀짝이 반대다.
번호와 자식 수의 홀짝이 다르려면 번호와 차수의 홀짝은 같아야 한다.
노드 번호의 홀짝 = 차수의 홀짝따라서 하나의 트리에서 다음 조건이 성립해야 한다.
번호와 차수의 홀짝이 다른 노드가 정확히 1개그 노드를 루트로 정하면 역홀짝 트리가 된다.
조건 정리
하나의 트리에서 다음 값을 세자.
same_count = 번호와 차수의 홀짝이 같은 노드 수
different_count = 번호와 차수의 홀짝이 다른 노드 수판별 조건은 다음과 같다.
| 트리 종류 | 가능한 조건 |
|---|---|
| 홀짝 트리 | same_count == 1 |
| 역홀짝 트리 | different_count == 1 |
전체 노드 수를 tree_size라고 하면 다음 관계를 사용할 수 있다.
different_count = tree_size - same_count포레스트의 트리를 구분하는 방법
입력은 하나의 트리가 아니라 여러 개의 트리로 구성된 포레스트다.
따라서 각 노드가 어느 트리에 속하는지 구분해야 한다.
이 문제에서는 Union-Find 자료구조를 사용할 수 있다.
간선 [a, b]가 주어질 때마다 두 노드가 같은 트리에 속하도록 합친다.
union(a, b)모든 간선을 처리한 뒤 각 노드의 대표 노드를 구하면 같은 대표 노드를 가진 노드들이 하나의 트리를 구성한다.
노드 번호를 배열 인덱스로 변환하기
노드 번호는 최대 1,000,000이고 연속적이지 않을 수 있다.
예를 들어 다음과 같은 노드 번호가 주어질 수 있다.
nodes = [3, 100, 999999]노드 번호를 그대로 배열 인덱스로 사용하면 불필요한 공간이 생긴다.
따라서 실제 노드 번호를 0부터 시작하는 인덱스로 변환한다.
index = {
node: i
for i, node in enumerate(nodes)
}예를 들면 다음과 같다.
3 -> 0
100 -> 1
999999 -> 2차수 계산
무방향 간선 [a, b]가 있으면 두 노드의 차수가 각각 1씩 증가한다.
degree[a_index] += 1
degree[b_index] += 1차수 계산과 Union-Find 병합을 같은 반복문에서 처리할 수 있다.
for a, b in edges:
a_index = index[a]
b_index = index[b]
degree[a_index] += 1
degree[b_index] += 1
union(a_index, b_index)전체 코드
def solution(nodes, edges):
node_count = len(nodes)
# 실제 노드 번호를 0부터 시작하는 인덱스로 변환한다.
index = {
node: i
for i, node in enumerate(nodes)
}
parent = list(range(node_count))
union_size = [1] * node_count
degree = [0] * node_count
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def union(a, b):
root_a = find(a)
root_b = find(b)
if root_a == root_b:
return
if union_size[root_a] < union_size[root_b]:
root_a, root_b = root_b, root_a
parent[root_b] = root_a
union_size[root_a] += union_size[root_b]
# 각 노드의 차수를 계산하고 같은 트리의 노드를 합친다.
for a, b in edges:
a_index = index[a]
b_index = index[b]
degree[a_index] += 1
degree[b_index] += 1
union(a_index, b_index)
tree_size = {}
same_parity_count = {}
for i, node in enumerate(nodes):
root = find(i)
tree_size[root] = tree_size.get(root, 0) + 1
same_parity_count.setdefault(root, 0)
# 노드 번호와 차수의 홀짝이 같은지 확인한다.
if node % 2 == degree[i] % 2:
same_parity_count[root] += 1
odd_even_tree_count = 0
reverse_tree_count = 0
for root, size in tree_size.items():
same_count = same_parity_count[root]
different_count = size - same_count
# 번호와 차수의 홀짝이 같은 노드가 유일한 경우
if same_count == 1:
odd_even_tree_count += 1
# 번호와 차수의 홀짝이 다른 노드가 유일한 경우
if different_count == 1:
reverse_tree_count += 1
return [odd_even_tree_count, reverse_tree_count]Union-Find 구현 설명
find
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return xfind는 노드가 속한 집합의 대표 노드를 찾는다.
경로 압축을 적용해 이후 탐색을 빠르게 만든다.
union
def union(a, b):
root_a = find(a)
root_b = find(b)
if root_a == root_b:
return
if union_size[root_a] < union_size[root_b]:
root_a, root_b = root_b, root_a
parent[root_b] = root_a
union_size[root_a] += union_size[root_b]union은 두 노드가 속한 집합을 하나로 합친다.
작은 집합을 큰 집합 아래에 붙여 트리 높이가 불필요하게 커지는 것을 방지한다.
하나의 트리가 두 종류 모두 될 수 있는 경우
하나의 트리가 홀짝 트리와 역홀짝 트리 두 종류 모두 될 수도 있다.
두 조건은 다음과 같다.
same_count == 1
different_count == 1두 조건을 동시에 만족하려면 전체 노드 수가 2개여야 한다.
tree_size = same_count + different_count = 2따라서 노드가 2개인 트리에서는 두 노드의 번호와 차수 관계에 따라 두 종류 모두 가능할 수 있다.
문제에서는 각 트리가 두 종류에 각각 해당하는지를 독립적으로 세어야 한다.
그래서 다음 두 조건을 if-elif가 아닌 별도의 if문으로 작성한다.
if same_count == 1:
odd_even_tree_count += 1
if different_count == 1:
reverse_tree_count += 1간선이 없는 노드
포레스트에는 간선이 하나도 연결되지 않은 단독 노드가 있을 수 있다.
단독 노드의 차수는 0이다.
해당 노드를 루트로 정하면 자식 수도 0이다.
노드 번호가 짝수인 경우
노드 번호: 짝수
자식 수: 0, 짝수따라서 홀짝 트리가 된다.
노드 번호가 홀수인 경우
노드 번호: 홀수
자식 수: 0, 짝수따라서 역홀짝 트리가 된다.
Union-Find의 초기 상태에서는 각 노드가 자기 자신을 대표 노드로 가지므로 단독 노드도 자동으로 하나의 트리로 처리된다.
시간 복잡도
노드 수를 N, 간선 수를 E라고 하자.
노드 번호 인덱스 맵을 만드는 데 다음 시간이 걸린다.
O(N)모든 간선을 처리하며 차수를 계산하고 Union-Find 연산을 수행한다.
O(E × α(N))α(N)은 역 아커만 함수로, 실제 입력 범위에서는 거의 상수로 볼 수 있다.
모든 노드를 한 번 순회해 트리별 정보를 집계한다.
O(N × α(N))따라서 전체 시간 복잡도는 사실상 다음과 같다.
O(N + E)공간 복잡도는 노드별 배열과 딕셔너리를 저장하므로 다음과 같다.
O(N)간선 정보를 별도의 인접 리스트로 저장하지 않기 때문에 입력 크기가 커도 메모리를 효율적으로 사용할 수 있다.
정리
이 문제는 모든 노드를 루트 후보로 직접 시도하면 비효율적이다.
루트 여부에 따라 자식 수의 홀짝이 어떻게 바뀌는지 관찰하면 루트를 직접 설정하지 않고도 판별할 수 있다.
핵심은 다음과 같다.
- 루트의 자식 수는 차수와 같다.
- 루트가 아닌 노드의 자식 수는
차수 - 1이다. 차수 - 1은 차수와 홀짝이 반대다.- 번호와 차수의 홀짝이 같은 노드가 정확히 하나라면 홀짝 트리가 가능하다.
- 번호와 차수의 홀짝이 다른 노드가 정확히 하나라면 역홀짝 트리가 가능하다.
- Union-Find로 포레스트의 각 트리를 구분한다.
루트 후보를 하나씩 검사하지 않고, 각 트리 안에서 번호와 차수의 홀짝 관계만 세는 것이 핵심이다.
