백준 2623 음악프로그램 위상정렬 알고리즘

 

from collections import deque
n, m = map(int, input().split())
arry = [[] for i in range(m)]
for i in range(m):
    arry[i] = list(map(int, input().split()))
    arry[i].pop(0)
adj = [[] for i in range(n+1)]
pan = 0
for i in range(m):
    for j in range(len(arry[i])):
        for k in range(j):
            if arry[i][j] not in adj[arry[i][k]]:
                adj[arry[i][k]].append(arry[i][j])
queue = deque()
stack = deque()
temp = 0
visit = [0]*(n+1)
dis = [-1]*(n+1)
finish = [0]*(n+1)
cont = 0
def dfs(s):
    global queue, visit, pan, cont,dis,finish
    dis[s] = cont
    cont += 1
    visit[s] = 1
    for i in range(len(adj[s])):
        if visit[adj[s][i]] == 0 and dis[adj[s][i]] == -1:
            dfs(adj[s][i])
        elif dis[adj[s][i]] != -1 and finish[adj[s][i]] == 0:
            pan = 1
    finish[s] = 1
    queue.append(s)
for i in range(1, n+1):
    if visit[i] == 0: dfs(i)
for i in reversed(queue) if pan == 0 else [0]:
    print(i)

전형적인 위상정렬 문제이다.

dfs를 이용하여 위상정렬을 한 뒤 그 속에서 사이클을 찾는 것이다.

하지만 사이클을 찾는 것에서 잘못풀어서 5번이나 틀렸다.

블로그 글을 참고하여 사이클을 판별하였더니 성공하였다.

각각 가수 순서를 기준으로 유향그래프(DAG사이클 X)를 만든 뒤(adj배열 이용) 

재귀 dfs를 돌려 큐에 넣어주면된다. 이때 dis, finish를 이용해 사이클을 판별한다.