728x90
분석
[1516번] 게임 개발하기 (위상정렬)
1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다.
karla.tistory.com
풀이
"""
첫 번째 줄에 전체 일의 개수 N과 일의 순서 정보의 개수 M이 주어집니다.
두 번째 줄부터 M개의 정보가 주어집니다.
6 6
1 4
5 4
4 3
2 5
2 3
6 2
전체 일의 순서를 출력합니다.
1 6 2 5 4 3
"""
import sys
input=sys.stdin.readline
from collections import deque
# 일의개수, 순정보개수
n,m= map(int, input().split())
# 진입 차수 리스트
dList = [0] * (n+1)
# 인접 리스트
a = [[] for _ in range(n+1)]
for i in range(1, m+1):
s,e=map(int, input().split())
a[s].append(e)
dList[e]+=1
queue = deque()
for i in range(1, n+1):
if dList[i] == 0:
queue.append(i)
while queue:
node = queue.popleft()
print(node, end=" ")
for i in a[node]:
dList[i]-=1
if dList[i] == 0:
queue.append(i)
728x90