Baekjoon 2623. 음악프로그램 / Python

2623. 음악프로그램

난이도 : 골드 3
소요 시간 : 30분
날짜 : 2024.12.19
언어 : Python
알고리즘 유형 : 위상정렬, 그래프이론, 방향비순환 그래프

설명 보기전에 문제 풀어보러 가기

1. 문제 설명

1. 순서가 주어진 리스트 여러개가 주어진다.
2. 이 순서를 유지하면서 주어진 모든 수를 정렬한다.

2. 해결 방식

1. 위상정렬의 아주 대표적인 문제이다.
2. 위상정렬알고리즘의 풀이방식을 그대로 사용한다.
3. 연결리스트 자료구조를 만들어 풀이할 수도 있을 것 같아서 해봤다. (사실 더 효율적이어서 한건 아니고, 이런 자료구조를 만드는 것에 익숙해지기 위해서 했다.)

3. 정답 코드

풀이 1 -  위상정렬

import sys
sys.stdin = open("C:/Users/ghtjd/Desktop/tmp/python/input.txt", "r")

# input = sys.stdin.readline

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

arr = [[] for _ in range(n + 1)]
visit = [0] * (n + 1)

for _ in range(m):
    pd_arr = list(map(int, input().split()))
    for singer in range(1, pd_arr[0]):
        arr[pd_arr[singer]].append(pd_arr[singer + 1])
        visit[pd_arr[singer + 1]] += 1

un_nominated = []
for i in range(1, n + 1):
    if visit[i] == 0: un_nominated.append(i)

res = []

while un_nominated:
    now = un_nominated.pop()
    res.append(str(now))

    for i in arr[now]:
        visit[i] -= 1
        if visit[i] == 0:un_nominated.append(i)

if len(res) == n:
    print('\n'.join(res))
else:
    print(0)

풀이 2 - 연결 리스트

import sys

# sys.stdin = open("C:/Users/ghtjd/Desktop/tmp/python/input.txt", "r")

input = sys.stdin.readline

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class SingerOrder:
    def __init__(self, n):
        self.heads = [None] * (n + 1)
        self.in_degree = [0] * (n + 1)
        self.n = n

    def add_order(self, before, after):
        if self.heads[before] is None:
            self.heads[before] = Node(after)
        else:
            now = self.heads[before]
            while now.next:
                now = now.next
            now.next = Node(after)
        self.in_degree[after] += 1

    def topological_sort(self):
        res = []
        q = []

        for i in range(1, self.n + 1):
            if self.in_degree[i] == 0:
                q.append(i)

        while q:
            now = q.pop(0)
            res.append(str(now))

            new_node = self.heads[now]
            while new_node:
                self.in_degree[new_node.value] -= 1
                if self.in_degree[new_node.value] == 0:
                    q.append(new_node.value)
                new_node = new_node.next

        if len(res) == self.n:
            return '\n'.join(res)
        else:
            return 0

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

singer_order = SingerOrder(n)

for _ in range(m):
    pd_arr = list(map(int, input().split()))
    for singer in range(1, pd_arr[0]):
        singer_order.add_order(pd_arr[singer], pd_arr[singer + 1])

print(singer_order.topological_sort())