💡문제
방향성 없는 그래프에서 어떤 정점에 물려 있는 변의 수를 차수(degree)라고 한다. 예를 들어 아래 갈은 그래프에서 정점 A와 D의 차수는 3, B와 C의 차수는 2이다.
그래프가 주어졌을 때, 정점의 차수들을 정점 번호 순서대로 나열하면 하나의 수열을 얻을 수 있다. 이러한 수열을 차수열(degree sequence)라고 하는데, 위와 같은 그래프의 차수열은 3, 2, 2, 3이라고 할 수 있다. 임의의 그래프의 차수열이 주어졌을 때, 이러한 차수열을 갖는 그래프를 구하는 프로그램을 작성하시오. 그래프의 간선은 방향성이 없으며, 자기 자신으로 돌아오는 간선은 없어야 한다. 그래프가 반드시 연결되어 있을 필요는 없으나, 차수열이 정점 순서대로 반드시 대응되어야 한다.
입력
첫째 줄에 N(2 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 차수열을 이루는 N개의 정수가 빈칸을 사이에 두고 주어진다. 차수열의 정수는 N-1보다 작거나 같은 음 아닌 정수이다.
출력
첫째 줄부터 N개의 줄에 걸쳐 그래프의 인접 행렬을 출력한다. 인접 행렬은 0 또는 1로 이루어지며, 답이 여러 개인 경우는 그 중에 하나만 출력하면 된다. 그래프가 존재하지 않는 경우에는 첫째 줄에 -1만을 출력한다.
예제입력
4
3 2 2 3예제출력
0 1 1 1
1 0 0 1
1 0 0 1
1 1 1 0📖내가 작성한 Code
import sys
'''
2초 128mb
'''
def main():
inputs = map(int, sys.stdin.read().split())
n = next(inputs)
graph = [[i,next(inputs)] for i in range(n)]
result = [[0] * n for _ in range(n)]
while True:
graph.sort(key=lambda x:x[1], reverse=True)
node, number = graph[0]
if number == 0:
break
if number + 1 > n:
return '-1'
for i in range(1,number+1):
if graph[i][1] == 0:
return '-1'
graph[0][1] -= 1
graph[i][1] -= 1
result[node][graph[i][0]] = 1
result[graph[i][0]][node] = 1
return "\n".join([" ".join(map(str,result[i])) for i in range(n)])
if __name__ == '__main__':
sys.stdout.write(main())
✍️풀이과정
처음 이 문제를 봤을 때, 쉬울 줄 알고 도전했는데 2시간이나 걸렸다. 그냥 단순하게 생각해서 많은 간선들을 점점 줄여나가는 방식을 사용하였다. 그런데, 계속 실패. 아래는 처음 실패한 로직이다.
def main():
inputs = map(int, sys.stdin.read().split())
n = next(inputs)
graph = sorted([[i,next(inputs)]for i in range(n)],key= lambda x:x[1], reverse = True)
result = [[0]*n for _ in range(n)]
for idx in range(n):
node, number = graph[idx][0], graph[idx][1]
if (end := idx + number + 1) > n:
return '-1'
if number == 0:
continue
for i in range(idx+1,end):
if graph[i][1] > 0:
graph[i][1] -= 1
result[node][graph[i][0]] = 1
result[graph[i][0]][node] = 1
else:
return '-1'
return "\n".join([" ".join(map(str,result[i])) for i in range(n)])반례는
5
2 2 1 1 1
따라서, 한 번 돌때마다 sort를 해줘야한다는 사실을 알게 되었다. 따라서 while 문으로 sort 하고 로직을 돌리는 식으로 구현. 코드 치다가 열이 너무 받아서 함수 분리 안하고 그냥 바로 완 침.
당당하게 3등
🧠 코드 리뷰
-
함수 분리의 필요성: 현재 모든 로직이 main()로직에 집중되어 있습니다. 입력 처리, 그래프 생성, 결과 계산 등을 별도의 함수로 분리하면 코드의 재사용성과 가독성이 향상됩니다.
-
정렬 및 우선순위 처리: graph.sort(key=lambda x: x[1], reverse=True)를 사용하여 매번 그래프를 정렬하고 있습니다. 이는 시간 복잡도를 증가시킬 수 있으므로, 우선순위 큐(힙)를 활용하여 효율성을 높일 수 있습니다.
🛠️AI 개선 코드
import sys
import heapq
def read_input():
n = int(input())
numbers = list(map(int, input().split()))
return n, numbers
def initialize_graph(n, numbers):
graph = []
for i in range(n):
if numbers[i] > 0:
graph.append([i, numbers[i]])
return graph
def process_graph(n, graph):
result = [[0] * n for _ in range(n)]
heapq.heapify(graph)
while graph:
node, number = heapq.heappop(graph)
if number == 0:
break
if number + 1 > n:
return -1
for i in range(1, number + 1):
if graph[i][1] == 0:
return -1
graph[0][1] -= 1
graph[i][1] -= 1
result[node][graph[i][0]] = 1
result[graph[i][0]][node] = 1
return result
def main():
n, numbers = read_input()
graph = initialize_graph(n, numbers)
result = process_graph(n, graph)
if result == -1:
print(-1)
else:
for row in result:
print(" ".join(map(str, row)))
if __name__ == '__main__':
main()
💻결과
🖱️참고 링크
