문제

[백준] 줄 세우기 (Gold 3)

요약

  • N명의 학생들 중 두 학생씩 뽑아 키를 비교한 정보가 주어진다.
  • 일부 학생들의 키를 비교한 결과가 주어지면, 키순으로 줄을 세우자.
  • 답이 여러 가지인 경우 아무거나 출력한다.

분류

  • 위상 정렬

풀이

1. 내 풀이 (위상 정렬)

  • 각 학생을 노드로, 두 학생의 키를 비교한 결과를 아크(arc)로 하는 방향그래프를 구현한다.
  • 아크는 키가 더 작은 쪽에서 더 큰 쪽으로 진입하도록 표현하자.
  • 진입차수(외부 노드에서 들어오는 아크의 수)가 0인 노드(학생)부터 위상 정렬을 실시하자.
  • 노드의 진입차수가 0이 되는 순서대로 출력한다.


from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
cnts = [0] * n
graph = [[] for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    graph[a - 1].append(b - 1)
    cnts[b - 1] += 1

queue = deque()

for i, c in enumerate(cnts):
    if c == 0:
        queue.append(i)
ans = []
while queue:
    v = queue.popleft()
    ans.append(v + 1)

    for i in graph[v]:
        cnts[i] -= 1
        if cnts[i] == 0:
            queue.append(i)

print(*ans)