음악프로그램 [백준 2623] - python

import sys
input = sys.stdin.readline

def BOJ2623() :
  N, M = map(int, input().split())
  graph = [[] for _ in range(N+1)]
  count_of_line = [0] * (N+1)
  queue = []
  answer = []
  
  for _ in range(M) :
    temp = list(map(int, input().split()))
    _, b = temp[:2]
    temp_list = temp[2:]
    for i in temp_list :
      graph[b].append(i)
      count_of_line[i] += 1
      b = i

  for i in range(1, N+1) :
    if count_of_line[i] == 0 :
      queue.append(i)
      answer.append(i)

  while queue :
    temp = queue.pop(0)
    for i in graph[temp] :
      count_of_line[i] -= 1
      if count_of_line[i] == 0 :
        queue.append(i)
        answer.append(i)
  
  if len(answer) != N :
    print(0)
  else :
    for i in answer :
      print(i)

BOJ2623()

 

접근 방법 :

1. 위상정렬의 기본적인 문제이다. 위상정렬의 알고리즘 동작에 대한 내용은 이전 포스팅에서 진행하였어서 따로 적진 않으려 한다.

2. 입력을 처리하는 부분만 조금 까다로웠다. 

3. 2번만 잘 처리하고 나면 진입차수가 0인것부터 차례대로 접근하는 위상정렬의 기본 문제라 생각한다.

위상 정렬을 코드로 그려내는 것만 익숙하다면 해당 문제는 어렵지 않게 풀 수 있지 않을까 싶다.

 

 

 

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

2623번: 음악프로그램