songining
Published 2021. 5. 20. 13:55
μœ„μƒμ •λ ¬ ALGORITHM

μœ„μƒμ •λ ¬ μ•Œκ³ λ¦¬μ¦˜

 

-큐λ₯Ό 이용

1. μ§„μž…μ°¨μˆ˜κ°€ 0인 λͺ¨λ“  λ…Έλ“œλ₯Ό 큐에 λ„£λŠ”λ‹€. 

2. 큐가 빌 λ•ŒκΉŒμ§€ λ‹€μŒμ˜ 과정을 λ°˜λ³΅ν•œλ‹€.

   1) νμ—μ„œ μ›μ†Œλ₯Ό κΊΌλ‚΄ ν•΄λ‹Ή λ…Έλ“œμ—μ„œ λ‚˜κ°€λŠ” 간선을 κ·Έλž˜ν”„μ—μ„œ μ œκ±°ν•œλ‹€.

   2) μƒˆλ‘­κ²Œ μ§„μž…μ°¨μˆ˜κ°€ 0이 된 λ…Έλ“œλ₯Ό 큐에 λ„£λŠ”λ‹€. 

 

--> 결과적으둜 각 λ…Έλ“œκ°€ 큐에 λ“€μ–΄μ˜¨ μˆœμ„œκ°€ μœ„μƒ 정렬을 μˆ˜ν–‰ν•œ 결과와 κ°™λ‹€. 

 

(νŠΉμ§•)

- 사이클이 μ—†λŠ” λ°©ν–₯κ·Έλž˜ν”„(DAG)μ—¬μ•Ό ν•œλ‹€.

- ν•œ λ‹¨κ³„μ—μ„œ 큐에 μƒˆλ‘­κ²Œ λ“€μ–΄κ°€λŠ” μ›μ†Œκ°€ 2개 이상인 κ²½μš°κ°€ μžˆλ‹€λ©΄ μ—¬λŸ¬κ°€μ§€ λ‹΅ 쑴재.

- λͺ¨λ“  μ›μ†Œλ₯Ό λ°©λ¬Έν•˜κΈ° 전에 큐가 λΉˆλ‹€λ©΄ 사이클이 μ‘΄μž¬ν•œλ‹€κ³  νŒλ‹¨ν•  수 있음 

 

(μ‹œκ°„λ³΅μž‘λ„)

- μ°¨λ‘€λŒ€λ‘œ λͺ¨λ“  λ…Έλ“œλ₯Ό ν™•μΈν•˜λ©° 각 λ…Έλ“œμ—μ„œ λ‚˜κ°€λŠ” 간선을 μ°¨λ‘€λŒ€λ‘œ μ œκ±°ν•˜λ―€λ‘œ μ‹œκ°„λ³΅μž‘λ„λŠ” O(V+E)이닀. 

 

μœ„μƒμ •λ ¬ μ½”λ“œ  

<python />
from collections import defaultdict, deque def topologicalSort(graph, level,n): queue = deque() for i in range(1,n+1): if level[i] == 0: queue.append(i) while queue: v = queue.popleft() print(v, end=' ') for i in graph[v]: level[i] -= 1 if level[i] == 0: queue.append(i) def main(): n, m = map(int, input().split()) graph = defaultdict(list) level = defaultdict(int) for i in range(m): a, b = map(int,input().split()) graph[a].append(b) level[b] += 1 topologicalSort(graph, level,n) if __name__ == '__main__': main()