[백준 / Python] 음악프로그램_2623

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

 

 

제출 코드

from _collections import deque
 
n, m = map(int, input().split())
data = [[] for _ in range(n + 1)]
indegree = [0 for _ in range(n + 1)]
flag = True
for _ in range(m):
    pd_data = list(map(int, input().split()))
    for i in range(1, len(pd_data) - 1):
        data[pd_data[i]].append(pd_data[i + 1])
        indegree[pd_data[i + 1]] += 1
 
result = []
 
 
def topology_sort():
    q = deque()
    for i in range(1, n + 1):
        if indegree[i] == 0:
            q.append(i)
    while q:
        node = q.popleft()
        result.append(node)
 
        for i in data[node]:
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)
 
 
topology_sort()
if len(result) != n:
    print(0)
else:
    for i in result:
        print(i)
 

 

 

 

처음 잘못 접근했던 방식

"경우에 따라서 남일이가 모두를 만족하는 순서를 정하는 것이 불가능할 수도 있다." 이 부분을 잘 생각 했어야 했다.

처음에는 이 부분을 고려해주기 위해서 서로 양방향으로 간선이 이루어져 있는지만 판별하면 되는 줄 착각했다.

 

순서를 정하는 것이 불가능한 상황이 나오려면 어떻게 되어야 할까?

바로 사이클이 발생하는 경우이다. 싸이클이 발생하면, indegree가 전부 0이 아니게 될 것이고 len(result) != n이 될 것이다.

양방향 간선인 것이 아니라, 사이클이 발생하는지를 판별하면 되었다.