intro
๐ข ์์ ์ ๋ ฌ = ์ฌ์ดํด์ด ์๋ ๋ฐฉํฅ ๊ทธ๋ํ(DAG; Directed Acyclic Graph)์ ๋ชจ๋ ๋ ธ๋๋ฅผ ๋ฐฉํฅ์ฑ์ ๊ฑฐ์ค๋ฅด์ง ์๋๋ก ์์๋๋ก ๋์ดํ๋ ๊ฒ
→ ์์ ์ ๋ ฌ์ DAG์ ๋ํด์๋ง ์ํํ ์ ์๋ค
→ ์ฌ๋ฌ ๊ฐ์ง ๋ต์ด ์กด์ฌํ ์ ์๋ค. ํ ๋จ๊ณ์์ ํ์ ์๋กญ๊ฒ ๋ค์ด๊ฐ๋ ์์๊ฐ 2๊ฐ ์ด์์ธ ๊ฒฝ์ฐ(๋ฌธ์ ์์ ์ค๋ฆ์ฐจ์, ๋ด๋ฆผ์ฐจ์ ๋ช ์ ์๋ค๋ฉด) ์ฌ๋ฌ ๊ฐ์ง ์์์ ๋ ฌ ๋ ธ๋ ๊ฒฐ๊ณผ๊ฐ ์กด์ฌ ๊ฐ๋ฅ
→ ๋ชจ๋ ์์๋ฅผ ๋ฐฉ๋ฌธํ๊ธฐ ์ ์ queue๊ฐ ๋น๋ค๋ฉด ์ฌ์ดํด์ด ์กด์ฌํ๋ค๊ณ ํ๋จ ๊ฐ๋ฅ(์ฌ์ดํด์ ํฌํจ๋ ์์ ์ค์์ ์ด๋ ํ ์์๋ queue์ ๋ค์ด๊ฐ์ง ๋ชปํ๋ค) (๋๋ queue์์ ๋ ธ๋๋ฅผ ๋ฝ์ ๋๋ง๋ค ๋ฝ์ ๋ ธ๋์ ๊ฐ์๊ฐ ์นด์ดํธ ๋์ด์, ์ต์ข ์นด์ดํธ ๋ ๋ ธ๋์ ๊ฐ์์ ๊ทธ๋ํ ์ ์ฒด ๋ ธ๋์ ๊ฐ์๊ฐ ๊ฐ์ ์ง ๋ค๋ฅธ ์ง ๋น๊ต๋ก๋ ์ ์ ์์)
→ ์คํ์ ํ์ฉํ DFS๋ฅผ ์ด์ฉํด ์์ ์ ๋ ฌ ์ํ๋ ๊ฐ๋ฅ
๐ข ์์์ ๋ ฌ ์๊ฐ ๋ณต์ก๋: O(V+E)๋ก ๊ฐ์ ๊ณผ ๋ ธ๋์ ๊ฐ์๊ฐ ์ ์ฒด ์๊ฐ๋ณต์ก๋. ๊ฐ๊ฐ ๋ ธ๋์ ๊ฐ์ ์ ํ ๋ฒ์ฉ ํ์ธํ๊ธฐ ๋๋ฌธ์ด๋ค.
๐ข ์ง์ ์ฐจ์(Indegree): ํน์ ํ ๋ ธ๋๋ก ๋ค์ด์ค๋ ๊ฐ์ ์ ๊ฐ์ / ์ง์ถ์ฐจ์(Outdegree): ํน์ ํ ๋ ธ๋์์ ๋๊ฐ๋ ๊ฐ์ ์ ๊ฐ์
BFS topology sorting
โป BFS์ queue ์๋ฃ๊ตฌ์กฐ ์ฌ์ฉ
โ ์ง์ ์ฐจ์(Indegree)๊ฐ 0์ธ ๋ชจ๋ ๋ ธ๋๋ฅผ queue์ ๋ฃ๋๋ค.
โก queue๊ฐ ๋น ๋๊น์ง ์๋ 2๊ฐ์ง ๊ณผ์ ์ ๋ฐ๋ณตํ๋ค.
โก - 1. queue์์ ์์๋ฅผ ๊บผ๋ด ํด๋น ๋ ธ๋์์ ๋๊ฐ๋ ๊ฐ์ ์ ๊ทธ๋ํ์์ ์ ๊ฑฐํ๋ค(indegree ๊ฐ์ 1์ฉ ๊ฐ์)
โก - 2. ์๋กญ๊ฒ ์ง์ ์ฐจ์๊ฐ 0์ด ๋ ๋ ธ๋๋ฅผ queue์ ๋ฃ๋๋ค.
โข ๊ฒฐ๊ณผ์ ์ผ๋ก ๊ฐ ๋ ธ๋๊ฐ queue์ ๋ค์ด์จ ์์๊ฐ ์์ ์ ๋ ฌ์ ์ํํ ๊ฒฐ๊ณผ์ ๊ฐ๋ค.
โป ์์) ๊ทธ๋ํ๋ DAG(์ฌ์ดํด์ด ์๋ ๋ฐฉํฅ ๊ทธ๋ํ)๋ก ์ค๋น๋์ด์ผ ํ๋ค. ์ฌ์ดํด์ด ํฌํจ๋์ด ์๋ ๊ทธ๋ํ๋ผ๋ฉด, ์ฌ์ดํด์ด ํฌํจ๋์ด ์๋ ๋ชจ๋ ๋ ธ๋๋ ์ง์ ์ฐจ์๊ฐ 1 ์ด์์ด ๋๋ค.
โ Directed Acyclic Graph ์ค๋น
โก ์ง์ ์ฐจ์(indegree)๊ฐ 0์ธ ๋ ธ๋ 1 queue์ ๋ฃ๊ธฐ
โข ๋ ธ๋ 1์ queue์ ๊บผ๋ด๊ณ , ๋ ธ๋ 1์์ ๋๊ฐ๋ ๊ฐ์ (outdegree ๊ฐ์ ๋งํผ) ์ ๊ฑฐ
โฃ ์๋กญ๊ฒ ์ง์ ์ฐจ์๊ฐ 0์ด ๋ ๋ ธ๋ 2์ ๋ ธ๋ 5 queue์ ์ฝ์
โฃ ๋์ผ ๋ฐฉ๋ฒ์ผ๋ก ๋ ธ๋ 2๋ฅผ ๋นผ์ ๋ ธ๋ 2์์ ๋๊ฐ๋ ๊ฐ์ ์ ์ ๊ฑฐ / ๊ทธ๋ฆฌ๊ณ ์๋กญ๊ฒ ์ง์ ์ฐจ์๊ฐ 0์ด ๋ ๋ ธ๋ 3 queue์ ์ฝ์
โฃ ๊ทธ ๋ค์ ๋ ธ๋ 5๋ฅผ ๋นผ์ ๋์ผ ๋ฐฉ๋ฒ์ผ๋ก ๋ ธ๋ 6์ queue์ ์ฝ์
โฃ ๊ทธ ๋ค์ ๋ ธ๋ 3์ ๋นผ๊ณ , ์ดํ ์ง์ ์ฐจ์๊ฐ 0์ด ๋ ๋ ธ๋๋ ์์ผ๋ฏ๋ก ๊ทธ๋๋ก ์ ์ง
โฃ ๋ ธ๋ 6์ ๋นผ๊ณ , ๋์ผ ๋ฐฉ๋ฒ์ผ๋ก ๋ ธ๋ 4๋ฅผ queue์ ์ฝ์
โฃ ๋ ธ๋ 4๋ฅผ ๋นผ๊ณ , ๋์ผ ๋ฐฉ๋ฒ์ผ๋ก ๋ ธ๋ 7์ queue์ ์ฝ์
โฃ ๋ ธ๋ 7์ ๊บผ๋.
∴ ์์ ์ ๋ ฌ ๊ฒฐ๊ณผ) queue์ ์ฝ์ ๋ ์ ์ฒด ๋ ธ๋ ์์: 1 → 2 → 5 → 3 → 6 → 4 → 7
code
from collections import deque
v, e = map(int,input().split()) #number of vertices, number of edges
indegree = [0] * (v+1) #initialize it to 0 in all each nodes
graph = [[] for i in range(v+1)] #graph initialization
for _ in range(e): #in each edges
a,b = map(int,input().split()) #node a -> node b
graph[a].append(b)
indegree[b] += 1
def topology_sort():
result = []
q = deque()
#1. insert nodes in a queue having zero indegrees
for i in range(1,v+1):
if indegree[i] == 0:
q.append(i)
#2. repeat until emptying the queue
while q:
node = q.popleft()
result.append(node) #update result list
for i in graph[node]:
indegree[i] -= 1 #remove edges
if indegree[i] == 0: #insert nodes having 0 indegree
q.append(i)
for i in result:
print(i,end=' ')
topology_sort() #1 2 5 3 6 4 7
'''
7 8
1 2
1 5
2 3
2 6
3 4
4 7
5 6
6 4
'''
examples
โ <BOJ G3 2252 ์ค ์ธ์ฐ๊ธฐ> โ
: A๊ฐ B ์์ ์์ผ ํ๋, ์์๊ฐ ์ ํด์ง ๋ฐ์ดํฐ๋ ๋ ธ๋ A → ๋ ธ๋ B์ ์ฐ๊ฒฐ์ ๋์ ์ผ๋ก ๋ง๋ , ์์์ ๋ ฌ ๊ฒฐ๊ณผ ์ต์ข ์ถ๋ ฅ. ์์์ ๋ ฌ ๊ธฐ๋ณธ ๋ฌธ์
โ <BOJ G3 2623 ์์ ํ๋ก๊ทธ๋จ> โ
: 2252์ ๋์ผํ ์์์ ๋ ฌ ๊ต๊ณผ์ ๋ฌธ์ . ๋ค๋ง, A -> B -> C์ ๊ฐ์ด ๋ ๊ฐ ์ด์์ ์ฐ๊ฒฐ๋ node ์์๊ฐ ์ ํด์ง ๋ฌธ์ . ์ด ๋ graph์ indegree update๋ง ์ ์ค์ ํด์ฃผ๋ฉด ๋. ์ฒซ๋ฒ์งธ node๋ถํฐ ๋งจ ๋ ๋ฐ๋ก ์์ node๊น์ง๋ง graph update / indegree๋ ๊ทธ ๋ฐ๋๋ก ๋๋ฒ์งธ node๋ถํฐ ๋งจ ๋ node๊น์ง์ ๋ชจ๋ node์ indegree -=1๋ก update
โ <Leetcode Medium 207. Course Schedule> โ
: (index 0๋ถํฐ ์์ ์ฃผ์) b๋ฅผ ์ ์๊ฐํ๊ณ a๋ฅผ ์๊ฐ(b → a) acyclic graph๋ง ์์์ ๋ ฌ์ด ๊ฐ๋ฅํ๋ฏ๋ก, ๋ชจ๋ courses(๋ ธ๋)๋ฅผ ๋๋ผ ์ ์๋์ง, ์ฆ, ์์์ ๋ ฌ์ด ๊ฐ๋ฅํ์ง(=์ฌ์ดํด์ด ์กด์ฌํ์ง ์๋ ์ง) ๋ฌป๋ ๋ฌธ์ . ์ฌ์ดํด ์กด์ฌ ์ ๋ฌด ํ๋ณ์, queue์์ ๋บ ๋ ธ๋์ ๊ฐ์๋ฅผ ๊ณ์ ์ธ๊ณ , ์ต์ข ์ผ ๋ ธ๋์ ๊ฐ์์ ๊ทธ๋ํ ์ ์ฒด ๋ ธ๋์ ๊ฐ์๊ฐ ์๋ก ๊ฐ์ ์ง ๋ค๋ฅธ ์ง ๋น๊ตํ๋ฉด ๋๋ค.
โ <Leetcode Medium 210. Course Schedule II> โ
: ์ 207 ์์์ ๋ ฌ์ ์ฐ์ฅ์ ๋ฌธ์ . ์ง์ topology sort ๋ด์ฉ์ ์ถ๋ ฅํ๋ ๋ฌธ์ .
'Computer Science > Algorithms' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
๐ซ Prefix Sum (1) | 2024.09.06 |
---|---|
๐ฃ Fibonacci Sequence (0) | 2024.06.26 |
๐ฒ Divide&Conquer (1) | 2024.06.08 |
๐ Power by Divide and Conquer (1) | 2024.06.06 |
๐ฃ๏ธ Shortest Path in an Unweighted Graph (0) | 2024.05.23 |
๋๊ธ