음악프로그램(2623) - Python, 위상정렬

 

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

 

 

 

코드

 

from collections import deque

# 입력
N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]
indegree = [0] * (N + 1)

# 그래프 그리기
for i in range(1, M + 1):
    info = list(map(int, input().split()))
    num_singers = info[0]
    order = info[1:]

    for j in range(num_singers - 1):
        graph[order[j]].append(order[j + 1])
        indegree[order[j + 1]] += 1

queue = deque()
result = []

for i in range(1, N + 1):
    if indegree[i] == 0:
        queue.append(i)

while queue:
    current = queue.popleft()
    result.append(current)
    for next_node in graph[current]:
        indegree[next_node] -= 1
        if indegree[next_node] == 0:
            queue.append(next_node)

if len(result) == N:
    print("\n".join(map(str, result)))
else:
    print(0)

 

 

풀이

 

위상정렬을 활용한 문제입니다.

 

 

1. 그래프에서 진입 차수(indegree)를 계산합니다. 진입 차수는 각 노드로 들어오는 간선의 개수를 의미합니다.

 

2. 진입 차수가 0인 노드를 큐에 넣습니다.

 

3. 큐에서 노드를 하나씩 꺼내며, 해당 노드와 연결된 간선을 제거하고,

간선을 제거한 후 진입 차수가 0이 된 노드를 큐에 추가합니다.

 

그래프의 모든 노드를 처리하면 정렬이 완료됩니다.

 

 

사이클이 발생한다면 답이 나올 수 없는 경우입니다.

 

위상정렬이 정상적으로 진행된다면 정답을 구할 수 있습니다.

 

 

 

다음에 또 봐요