[백준] 2252번, python - 줄 세우기 (위상 정렬)

 

위상정렬에 관한 개념을 정확히 알지 못해서 문제를 푸는 데 어려움이 있었다.

 

위상정렬이란 방향 그래프에서 모든 간선 방향을 지키면서 노드를 나열하는 것을 의미한다.

단, 사이클이 없는 그래프에서만 가능하다!!

 

대표적인 알고리즘은 다음과 같다.

 

1. 모든 노드의 진입차수를 계산한다

2. 진입 차수가 0인 노드들을 큐에 추가한다

3. 큐에서 노드를 하나 꺼내서 해당 노드와 연결된 간선을 제거한다

4. 간선을 제거하여 진입 차수가 0이되면 다시 큐에 추가한다

5. 큐가 빌 때까지 반복한다.

 

여기서 진입 차수가 0이라는 것은 해당 노드보다 앞에 와야 할 노드가 없다는 뜻이다.

from collections import deque

n, m = map(int,input().split())
graph = [[] for _ in range(n+1)]
indegree = [0]*(n+1) # 진입 차수

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

queue = deque()
res = []

# 진입 차수 0인 노드부터 시작
for i in range(1, n+1):
    if indegree[i] == 0:
        queue.append(i)

while queue:
    now = queue.popleft()
    res.append(now)
    
    for next_node in graph[now]:
        indegree[next_node] -= 1 # 간선 제거
        if indegree[next_node] == 0: # 진입 차수가 0이되면 다시 큐에 추가 
            queue.append(next_node)

print(*res)