[Python] 8286번 Road Network 2

https://www.acmicpc.net/problem/8286

8286번: Road Network 2

---

 

23/09/23

 

 

차수열(Degree Sequence)의 개념을 익힐 수 있는 문제다.

 

여담으로 대회 개최를 준비하던 중 이 문제와 동일한 문제를 만들었고, 출제하려 했으나, 이 문제를 발견하게 되어서 문제를 버리게 되었다.

---

 

문제 접근 방식:

 

 

먼저, 노드의 차수에 대한 개념이 필요하다.

 

노드의 차수(Degree)란, 노드를 국소적으로(locally) 보았을 때, 그 노드에 연결 되어 있는 간선의 개수를 의미한다.

 

한 노드에 자기 자신을 연결하는 루프 간선이 있는 경우라면 이는 2개로 센다.(Local하게 보기 때문이다.)

 

 

두 번째로, Handshaking lemma에 대해 알아보자.

 

Handshaking lemma는 별거 아니고, 모든 노드의 차수를 더하면 간선 개수의 2배가 된다는 정리이다.

 

즉, 다음과 같은 수식으로 표현되는 정리다.

 

$$\sum_{v \in V} deg(v) = 2|E|$$

 

이 정리에 대한 직관적인 증명은 하나의 간선은 두 개의 노드에 연결되야 하므로, 하나의 간선이 전체 노드의 차수에 기여하는 크기는 2라는 사실로써 증명할 수 있다.

 

 

이제 트리를 생각해보자.

 

트리는 그래프 중에서 특별한 그래프로, 모두 연결되어 있고, 루프가 존재하지 않으며, 중복된 간선이 존재하지 않고, 사이클이 존재하지 않는 그래프이다.

 

사이클이 존재하지 않고, 중복된 간선이 존재하지 않기 때문에 $n$개의 노드를 가진 트리 $T$가 있다면, $T$는 간선의 개수가 $n-1$개임을 알 수 있다.

 

Handshaking lemma를 사용한다면, $\sum_{v \in T} deg(v) = 2n-2$임을 알 수 있다.

 

물론 각 노드의 차수(Degree)는 $1$보다 커야 한다.

 

즉, 트리라면 트리의 차수열의 합은 $2n-2$가 된다.

 

 

그 반대도 성립이 되는데, 양의 정수로만 이루어진 어떤 차수열(Degree Sequence)이 주어지고 그 차수열의 합이 $2n-2$라면, 트리를 만들 수 있다.

 

이에 대한 자세한 증명은 수학적 귀납법으로 확인할 수 있으며, 아래 링크를 참고해 보자.

---

https://gazelle-and-cs.tistory.com/42

그래프 트리에 관한 간단한 성질들

---

 

이제 이러한 사실들을 기반으로 하여 문제를 접근해 보자.

 

먼저, 차수열이 주어지면 이걸 가지고 트리를 만들 수 있는지 판단하는 기준은 $2n-2$가 되냐 안되냐로 구분할 수 있다.

 

만약 차수열의 합이 $2n-2$가 되지 않으면 트리를 만들 수 없으므로 문제에서 주어진 대로 "BRAK"을 출력하면 된다.

 

 

차수열의 합이 $2n-2$가 된다면 어떻게 구성해야 할까?

 

어떤 트리 $T$가 존재한다면 $T$에는 항상 $2$개 이상의 리프 노드가 존재한다. 또한, 리프 노드의 차수는 $1$임을 알고 있다.

 

또한 트리에서 리프 노드를 떼어내도 항상 리프 노드가 계속 생김을 알 수 있다.

 

이 사실과 위의 증명을 읽고 생각해 보면, 리프 노드와 리프 노드가 아닌 노드 중에서 가장 차수가 작은 노드를 이으면 항상 리프 노드가 생기기 때문에 이를 이용해서 트리를 구성하면 됨을 알 수 있다.

 

두 노드를 이으면 리프 노드는 리프 노드 셋에서 빼면 되고, 리프 노드가 아닌 노드는 차수를 $1$만큼 줄이고, 리프 노드가 된다면 리프 노드 셋에 넣고 그렇지 않으면 리프 노드가 아닌 리스트에 넣으면 된다.  

 

리프 노드가 아닌 노드 중에서 가장 차수가 작은 노드를 판단하는 건 넣고 빼는 연산이 계속 반복되기 때문에 우선순위 큐를 이용하여 구현할 수 있다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 8286번 Road Network 2
# 트리, 차수열
import sys
input = sys.stdin.readline
from heapq import heappop, heappush

N = int(input())
A = list(map(int, input().rstrip().split()))
if sum(A) != 2*N-2:
    print('BRAK')
else:
    leaf_set = set()
    not_leaf = []
    for i in range(N):
        if A[i] == 1:
            leaf_set.add(i+1)
        else:
            heappush(not_leaf, (A[i], i+1))
    while leaf_set:
        node1 = leaf_set.pop()
        if not_leaf:
            node_degree, node2 = heappop(not_leaf)
        else:
            node2 = leaf_set.pop()
            print(node1, node2)
            break
        if node_degree == 2:
            leaf_set.add(node2)
        else:
            heappush(not_leaf, (node_degree - 1, node2))
        print(node1, node2)