[백준] 2252 줄 세우기 - 위상 정렬 파이썬

문제

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

2252번: 줄 세우기

 

 

---

풀이

https://freedeveloper.tistory.com/390

[이것이 코딩 테스트다 with Python] 36강 위상 정렬

 

위상정렬 알고리즘

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

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

    2-1. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다

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

=> 결과 적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과와 같다

 

 

위상정렬 특징

• 사이클이 존재하지 않은 방향그래프에서만 수행가능
• 여러가지 답이 존재
• 스택&DFS로도 수행가능

 

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

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

#그래프 만들기
g = [[] for _ in range(n+1)]
indgree = [0]*(n+1)
for _ in range(m):
    a, b = map(int, input().split())
    g[a].append(b)
    indgree[b] += 1

#큐에 초기 진입차수 0인 노드 넣기
q = deque()
for i in range(1, n+1):
    if indgree[i] == 0:
        q.append(i)

#위상정렬
while q:
    now = q.popleft()
    print(str(now) + " ", end="")
    for i in g[now]:
        indgree[i] -= 1
        if indgree[i] == 0: #새롭게 진입차수 0이 된 노드 넣기
            q.append(i)