[백준] 줄 세우기

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

2252번: 줄 세우기

 

이렇게 또 하나를 배웠다. 위상 정렬로 조건(이미 정해진 순서)을 가지고 전체를 차례로 수행할 수 있는 경우를 구하는 방법이다. 문제는 위상 정렬이 가능한 경우만 주어지므로 사이클 등의 경우는 무시했다. 또한, 조건에 맞는 답은 여러 가지일 수 있다.

 

자신의 앞에 학생이 없는 경우(node[i] = 0)인 경우는 가장 먼저 올 수 있다. 이 학생들을 queue에 담아 queue에서 뺄 때(이때의 학생을 x라고 하자.), answer에 담은 후 x 뒤에 있는 학생들(conn[x]) 와의(학생 중 하나를 y라고 하자.) node[y] 를 1씩 빼준다. x 와의 관계를 끊는다는 의미로 이때, node[y] = 0이라면 y 앞에 학생이 없는 경우이므로 queue에 넣어준다. 이 작업을 반복하여 answer 을 반환하면 된다.

 

import sys
from collections import defaultdict, deque

N, M = map(int, sys.stdin.readline().split())
node = {}
conn = defaultdict(list)
queue = deque([])
answer = []

for i in range(1, N+1):
	node[i] = 0

for i in range(M):
	A, B = map(int, sys.stdin.readline().split())
	node[B] += 1
	conn[A].append(B)

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

while queue:
	x = queue.popleft()
	answer.append(str(x))

	for i in conn[x]:
		node[i] -= 1

		if node[i] == 0:
			queue.append(i)

print(' '.join(answer))