[BOJ, Python] 2252번_줄 세우기 With 위상 정렬

이 글은 Velog에서 이전한 글입니다. Velog 원문 보기

백준_2252번

문제 설명

N명의 학생들을 키 순서대로 줄을 세우려 한다. 학생 A가 학생 B보다 앞에 서야 한다는 M개의 키 비교 정보가 주어질 때, 올바른 줄 세우기 결과를 출력하라.

• 학생 번호는 1번부터 N번까지.
• 답이 여러 가지인 경우 아무거나 출력 가능.

---

알고리즘: 위상 정렬 (Topological Sort)

• 방향 그래프로 간선을 구성: A → B
• 진입 차수(in-degree)를 기록하고, 진입 차수가 0인 노드부터 출력
• 큐(BFS)를 이용해 순차적으로 정렬

---

논리 흐름

1. 학생 번호를 정점으로 간주
2. A → B 형태의 간선 구성
3. 진입 차수가 0인 노드를 큐에 삽입
4. 큐에서 꺼내면서 인접한 노드들의 진입 차수를 감소시키고, 0이 되면 다시 큐에 삽입
5. 모든 정점을 방문할 때까지 반복

---

정답 코드

import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import deque

N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
in_degree = [0]*(N+1)
q = deque()

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

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

result = []
while q:
    node = q.popleft()
    result.append(node)
    for next_node in graph[node]:
        in_degree[next_node] -= 1
        if in_degree[next_node] == 0:
            q.append(next_node)

print(*result)

시간 복잡도: O(N + M)

• 그래프 생성: O(M)
• 위상 정렬: O((N + M) log N)

---

참고

• 정답이 여러 개인 위상 정렬 문제에서 채점 시스템이 정해진 순서를 요구할 경우에는 heapq를 사용하여 사전순 정렬이 필요함
• 단순한 BFS 위상 정렬이라면 deque로도 충분하지만, 위 조건에서 실패할 수 있음