문제
https://www.acmicpc.net/problem/2252
풀이
https://freedeveloper.tistory.com/390
위상정렬 알고리즘
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)
'알고리즘 스터디' 카테고리의 다른 글
[백준] 3085 사탕 게임 - 파이썬 (0) | 2021.11.19 |
---|---|
[백준] 1789 수들의 합 - 파이썬 (0) | 2021.11.19 |
[백준] 16916 부분 문자열 - KMP 파이썬 (0) | 2021.11.07 |
[백준] 1197 최소 스패닝 트리 파이썬 (0) | 2021.11.06 |
[백준] 1916 최소비용 구하기 파이썬 (0) | 2021.11.05 |