[Python] 백준 2623 - 음악프로그램 문제 풀이

Overview

BOJ 2623번 음악프로그램 Python 문제 풀이
분류: Topological Sorting (위상정렬)

문제 페이지

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

풀이 코드

from sys import stdin
from collections import defaultdict, deque
from typing import List


graph = defaultdict(list)
indegrees = defaultdict(int)


def topology(n: int) -> List[int]:
    dq = deque()
    for i in range(1, n + 1):
        if indegrees[i] == 0:
            dq.append(i)

    res = []
    while dq:
        node = dq.popleft()
        res.append(node)
        for neighbor in graph[node]:
            indegrees[neighbor] -= 1
            if indegrees[neighbor] == 0:
                dq.append(neighbor)

    if len(res) < n:
        return [0]
    else:
        return res


def main():
    def input():
        return stdin.readline().rstrip()

    n, m = map(int, input().split())
    for _ in range(m):
        order = list(map(int, input().split()))
        for i in range(1, len(order) - 1):
            graph[order[i]].append(order[i + 1])
            indegrees[order[i + 1]] += 1

    print(*topology(n), sep="\n")


if __name__ == "__main__":
    main()

Topological Sorting을 이용하여 순서를 구한다.
각 pd별로 가수 순서를 입력 받으면 graph와 indegrees에 다음 가수와 진입 차수를 저장한다. 그 다음 진입 차수가 0인 가수들을 탐색하며 순서를 구한다.