[백준] 14567번 선수과목(python)

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

14567번: 선수과목 (Prerequisite)

 

1. 난이도 골드5 (🥇)

 

위상정렬을 이용해 문제를 풀었다.

 

위상정렬은 위 문제와 같이, 작업을 차례대로 수행해야 할 때 사용하는 알고리즘이다.

 

 

2. 내가 작성한 코드

import sys
from collections import deque

input = sys.stdin.readline

n,m = map(int, input().rstrip().split()) #n = 과목수 m = 선수 조건수
indegree = [0] * (n+1) #진입차수
subject = [[] for _ in range(n+1)] 

for i in range(m): #선수과목이 필요할 경우 +1
  a,b = map(int, input().rstrip().split())
  subject[a].append(b)
  indegree[b] +=1


def search():

  result = [1] * (n+1)
  q = deque()

  for i in range(1,n+1): 
    if indegree[i] == 0: #진입차수가 0이면 q에 넣기
      q.append(i)

  while q:
    now = q.popleft()

    for i in subject[now]: #now와 연결되어 있을 경우 학기는 +1, 진입차수는 -1
      result[i] = result[now] + 1
      indegree[i] -=1

      if indegree[i] == 0:
        q.append(i)

  for i in result[1:]:
    print(i, end=" ")
    
search()