[백준 2252번] 줄 세우기

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

2252번: 줄 세우기

2023.04.11 - [코딩 테스트/개념] - Topological sort

# 1 <= N <= 32000
# 1 <= M <= 100000
# no cycle, directed graph

import sys
from collections import deque

readline = sys.stdin.readline

N, M = map(int, readline().split())

graph = [[] for _ in range(N + 1)]
indegree = [0 for _ in range(N + 1)]
for i in range(1, M + 1):
    A, B = map(int, readline().split())  # A -> B
    graph[A].append(B)
    indegree[B] += 1

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

while len(tp) < N and queue:
    v = queue.popleft()
    tp.append(v)

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

print(" ".join(map(str, tp)))

진입 차수(in-degree)가 0인 노드를 골라서 위상 정렬 배열에 추가하고, 해당 노드와 연결된 인접 노드들을 인접 리스트를 통해 찾고 진입 차수를 1씩 감소시키는 방식으로 정렬이 이뤄진다. 

다만, 진입 차수가 0인 노드를 고를 때 while문 안에서 반복문으로 찾으면 시간 초과가 발생한다. 따라서 queue를 이용해 0인 노드들을 저장하고 꺼내서 사용하는 방식으로 수정했다.