[ baekjoon ] 음악프로그램 2623번 ( python )

문제

백준 2623 음악프로그램 풀이 ( 파이썬 )

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

2623번: 음악프로그램

 

풀이

순서라는 말을 들었을 때 단순히 위상정렬을 사용하면 되겠지라고 생각했는데 안 되는 경우를 생각해보니 싸이클이 생겼을 때였다. 그러므로 위상정렬을 하기 전에 먼저 싸이클이 있는지 확인하고 싸이클이 있다면 0을 출력하고 아니라면 순서를 출력하면 된다.

 싸이클을 판단할 때 어떤 노드를 골라야하나 생각해서 위상정렬의 시작은 차수가 0인 노드만 확인하면 될줄 알았지만 싸이클이 있는 방향이 어디인지 모르기 때문에 전 노드에서 검사를 했다. 말로 이해가 안 되면 아래 그림이 예시이다.

위의 그림에서 차수가 0인 노드는 1밖에 없으므로 위상정렬을 진행하더라도 싸이클이 생기는 부분을 검사하지 못한다.

from collections import deque

n,m=map(int,input().split())

graph=[[] for _ in range(n+1)]
indegree=[0]*(n+1)

visited=[0]*(n+1)

# 싸이클 검사 부분
def dfs(here):
    if visited[here]:
        if visited[here] ==-1:
            return True
        return False
    
    visited[here] = -1
    for node in graph[here]:
        if dfs(node):
            return True
    visited[here]=1
    return False

for i in range(m):
    arr=list(map(int,input().split()))
    for j in range(2,len(arr)):
        graph[arr[j-1]].append((arr[j]))
        indegree[arr[j]]+=1

q=deque()
for i in range(1,n+1):
    if indegree[i]==0:
        q.append(i)
        
# 싸이클 판단
flag=True

# 전 노드에서 싸이클 유무 검사
for i in range(1,n+1):
    if dfs(i):
        print(0)
        flag=False
        break
        
if flag:
    while q:
        now=q.popleft()
        print(now)
        for i in graph[now]:
            indegree[i]-=1
            if indegree[i]==0:
                q.append(i)