Computer Science/Algorithms

๐ŸŽข Topology Sort

metamong 2024. 10. 11.

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

๋Œ“๊ธ€