Baekjoon 2252. 줄 세우기 / Python

알고리즘 설명

문제 설명

n명의 학생들을 키 순서대로 줄을 세우는 문제
학생들의 키가 나와있지 않고, 키의 비교가 주어진다.

코드 설명

위상 정렬 알고리즘

1. 각 학생의 뒤에 있어야할 학생의 리스트와 각 학생의 앞에 있어야 할 학생 수 리스트를 만든다.
2. 학생의 앞에 있어야 할 학생 수가 0인 학생들을 큐에 넣고 위상정렬을 진행한다.
3. 반복

import sys
from collections import deque

input = sys.stdin.readline

# 입력 처리
n, m = map(int, input().split())
behind = [[] for _ in range(n + 1)]
front = [0] * (n + 1)

# 그래프 구성
for _ in range(m):
    a, b = map(int, input().split())
    behind[a].append(b)
    front[b] += 1

# 위상 정렬 초기화
res = []
q = deque()

# 진입 차수가 0인 노드를 큐에 삽입
for i in range(1, n + 1):
    if front[i] == 0:
        q.append(i)

# 위상 정렬 수행
while q:
    now = q.popleft()
    res.append(now)
    for next in behind[now]:
        front[next] -= 1
        if front[next] == 0:
            q.append(next)

# 결과 출력
print(*res)