[Python] 2084번 차수열

 

 

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

2084번: 차수열

---

 

24/01/19

 

 

이전에 차수열이 주어졌을 때 트리를 만드는 문제를 풀었었는데, 그 문제와 접근 방식이 동일하여 빠르게 아이디어를 떠올릴 수 있었던 문제였다.

 

다만, 이 문제는 우선순위 큐를 사용하여 구현하지 않고, 그때그때 마다 정렬하여 문제를 해결하여도 쉽게 풀리는 문제이기 때문에 그 문제보다 약간 낮은 난이도를 받은 것 같다.

 

나름 유명한 문제로, 그래프 이론을 조금 배웠다면 해결할 사람들은 쉽게 해결할 수 있는 문제였던 것 같다.

 

차수열이 주어졌을 때 트리를 만드는 문제에 대한 해설은 밑에 나와있다.

 

2023.09.26 - [알고리즘/백준 문제 풀이] - [Python] 8286번 Road Network 2

[Python] 8286번 Road Network 2

---

 

문제 접근 방식:

 

 

그리디적으로 접근하면 된다.

 

가장 많은 차수가 남은 노드 먼저 다른 노드에 에지를 분배하는 식으로 하면 된다.

 

예를 들어, 차수가 $4, 4, 4, 3, 2$라면, 차수 $4$짜리 노드를 나머지 $4$개의 노드에 연결한다.

 

그러면 나머지 노드들의 차수는 모두 하나씩 깎이므로, $0, 3, 3, 2, 1$이 된다.

 

그다음으로 가장 많은 차수를 지닌 노드의 차수는 $3$이므로, 이 노드에 나머지 $3$개의 노드를 연결한다.

 

그러면 $0, 0, 2, 1, 0$이 된다.

 

이후 가장 많은 차수를 지닌 노드의 차수는 $2$인데, 이 노드에 $2$개의 다른 노드를 연결할 수 없으므로, 이러한 차수열을 지닌 그래프는 만들 수 없다고 판단하는 것이다.

 

아이디어 자체는 쉽게 떠올렸지만 구현의 실수가 있어서 여러 번 틀렸었다.

 

매 과정을 진행할 때마다 가장 많은 차수를 지닌 노드의 차수를 구해야 하는데, 이를 매 번 정렬을 하지 않고 그냥 구현해서 틀린 구현을 했었다.

 

이 과정을 진행할 때마다 매 번 정렬을 진행해 주면 된다.

 

---

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

# 2084번 차수열
# 차수열, 그래프 이론, 구성적
'''
접근 방법:
일단 차수열을 정렬해
예를 들어 44432라면?
4부터 시작해서 분배해
3321
210
이후엔 불가능
이러한 과정을 반복하다가 불가능함을 판단하면 된다.
'''
import sys
input = sys.stdin.readline

N = int(input())
deg = list(map(int, input().rstrip().split()))
if sum(deg) % 2:
    print(-1)
    exit(0)
matrix = [[0 for _ in range(N)] for _ in range(N)]
while True:
    ordered_vertex = sorted(range(N), key = lambda x: deg[x], reverse = True)
    largest_vertex_num = ordered_vertex[0]
    largest_degree = deg[largest_vertex_num]
    if largest_degree == 0:
        break
    for i in range(1, largest_degree+1):
        if i >= N:
            print(-1)
            exit(0)
        vertex_num = ordered_vertex[i]
        if deg[vertex_num] == 0:
            print(-1)
            exit(0)
        deg[vertex_num] -= 1
        deg[largest_vertex_num] -= 1
        matrix[vertex_num][largest_vertex_num] = 1
        matrix[largest_vertex_num][vertex_num] = 1
for i in range(N):
    print(*matrix[i])