[ 백준 2623번 ] 음악프로그램 파이썬

---

[백준 2623번 음악 프로그램 바로가기]

2623번: 음악프로그램

1 큐를 이용한 위상정렬

논리

1. 진입차수가 0인 노드를 큐에 넣는다
2. 큐에서 꺼내면서 result에 순차적으로 기록하고, 해당 노드에 연결을 없앤다
3. 연결이 해제된 노드들 중 새로 진입차수가 0이 된 노드를 큐에 넣는다
4. 탐색 완료시 result의 개수가 총 노드의 개수보다 적으면 순환구조가 발생한 것이라 판단

2 dfs를 이용한 위상정렬

논리

1. 진입차수가 0인 노드부터 dfs진행(방문한 노드 기록하여 중복된 방문 방지)
2. 순환 구조 여부를 파악하기 위해 실시간 탐색 경로를 기록한다. 각 노드를 탐색할 때(진입 -> 하위 노드 탐색 -> 빠져나오기), 진입 단계에서 탐색경로에 추가하고, 빠져나올 때 탐색경로에서 제거한다 --> 다음 하위 노드가 탐색 경로에 존재하면 순환구조라고 판단
3. 각 노드 탐색 완료시(빠져나올 때) result에 역순으로 기록한다

코드

import sys
from collections import defaultdict, deque


# using queue
def music_queue(N, graph, in_degree):

    # enque nodes with 0 indegree
    q = deque()
    for node in range(1, N+1):
        if in_degree[node] == 0:
            q.append(node)

    # topological sorting using queue
    # remove nodes with 0 indegree --> enque new nodes with 0 indegree
    result = []
    while q:
        curr = q.popleft()
        result.append(curr)

        for next in graph[curr]:
            in_degree[next] -= 1
            if in_degree[next] == 0:
                q.append(next)


    if len(result) == N:
        print(*result, sep='\n')
    else:
        print(0)
    return


# using dfs(recursion)
def music_dfs(N, graph, in_degree):

    def _dfs(curr):

        # 순환구조시 탐색 안함
        if has_cycle[0]:
            return

        visited[curr] = True
        # 현재까지의 경로 기록
        route.append(curr)

        for next in graph[curr]:
            # 순환구조 판단
            if next in route:
                has_cycle[0] = True
            if not visited[next]:
                _dfs(next)
        # 노드 탐색 완료시 경로에서 pop하고, result에 추가
        route.pop()
        result.append(curr)


    visited = [False] * (N+1)   # 노드 방문 여부 기록
    route = []                  # 탐색 경로 기록
    has_cycle = [False]         # 순환구조여부 파악
    result = []

    for node in range(N+1):
        if not in_degree[node]: # 진입차수 0인 노드 탐색
            _dfs(node)

    if has_cycle[0]:            # 순환구조시 0 출력
        print(0)
    else:                        # 역순으로 출력
        print(*result[-1:-N-1:-1], sep='\n')
    return 

#########################################################

# inputs
N, M = map(int, sys.stdin.readline().split())
graph  = defaultdict(list)
in_degree = [0] * (N+1)
for _ in range(M):
    nums = list(map(int, sys.stdin.readline().split()))
    for i in range(1, nums[0]):
        in_degree[nums[i+1]] += 1
        graph[nums[i]].append(nums[i+1])

# 택 1
# music_queue(N, graph, in_degree)
# music_dfs(N, graph, in_degree)