[백준 2252번] 줄 세우기 - python

문제 링크

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

2252번: 줄 세우기

풀이 

- 위상 정렬 문제를 풀어보았다.

위상 정렬 이란 ? 

순서가 정해져 있는 작업을 차례대로 수행해야 할 때, 그 순서를 결정하기 위해 사용하는 알고리즘 

- 방향 그래프의 모드 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'이다.

- 진입 차수 : 특정한 노드로 들어오는 간선의 개수

- 알고리즘 

1. 진입차수가 0인 노드를 큐에 넣는다.

2. 큐가 빌 때까지 다음의 과정을 반복한다.

3. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.

4. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

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

# 위상정렬 알고리즘 
def topology_sort():
    result = []
    q = deque()
    
    for i in range(1,n+1):
        if indegree[i] == 0:
            q.append(i)

    while q :
        now = q.popleft()
        result.append(now)
        
        for i in graph[now]:
            indegree[i] -= 1 
            
            if indegree[i] == 0:
                q.append(i)
                
    print(*result)

n, m = map(int,input().split())

indegree = [0] * (n+1)
graph = [ [] for _ in range(n+1) ] 

for _ in range(m):
    a, b = map(int,input().split())
    # 진입 차수 증가 
    indegree[b] += 1 
    graph[a].append(b)
    
topology_sort()