[백준] 2252번 - 줄 세우기

---

문제 분석

학생들을 노드로 생각하고, 키 순서 비교 데이터로 에지를 만든다고 생각했을 때, 노드의 순서를 도출하는 가장 기본적인 문제이다. 특히 답이 여러 개일때 아무것이나 출력해도 된다는 전제는 위상 정렬의 결괏값이 항상 유일하지 않다는 알고리즘의 전제와 동일하다는 것을 알 수 있다.
따라서 위상정렬을 통해 해당 문제를 풀면 된다.

---

소스 코드

# 줄 세우기

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

N , M = map(int, input().split())
arr = [[] for _ in range(N + 1)]
getPointed = [0 for _ in range(N + 1)]
queue = deque()

for _ in range(M):
    A, B = map(int, input().split())
    arr[A].append(B)
    getPointed[B] += 1

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

while queue:
    value = queue.popleft()
    print(value, end=' ')
    for v in arr[value]:
        getPointed[v] -= 1
        if getPointed[v] == 0:
            queue.append(v)

위 코드에서는 getPointed 배열로 진입차수를 카운트 하고 있으며, 처음에는 진입차수의 값이 0, 즉 다른 노드(학생)를 고려하지 않고 먼저 나올 수 있는 값을 큐에 넣고,
해당 큐가 비어 있을 때 까지 진입차수 값을 빼주는 과정을 반복한다.