[알고리즘] 위상 정렬(Topological Sort)

위상 정렬이란?

사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미한다.

특정 공정을 수행하기 위해선 선행 되어야 하는 공정이 다 수행되어야 할 때 많이 쓰인다.

• 진입차수(Indegree): 특정한 노드로 들어오는 간선의 개수
• 진출차수(Outdegree): 특정한 노드에서 나가는 간선의 개수

위상 정렬의 특징

• 위상 정렬을 수행할 그래프는 사이클이 없는 방향 그래프(DAG)여야 한다.
• 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있다.
• 위상 정렬에는 여러가지 답이 존재할 수 있다.

💡위상 정렬 알고리즘 동작 과정

1. 진입차수가 0인 모든 노드를 큐에 넣는다.
2. 큐가 빌 때까지 다음의 과정을 반복한다.
   1. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
   2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

→ 결과적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과이다.

# 인접 행렬로 그래프가 표현되어 있을 때
from collections import deque

name=['cs','language','datastructure','algorithm','project','codingtest','to be a programmer']

arr = [
    [0,0,0,0,0,0,1],
    [0,0,1,1,0,0,0],
    [0,0,0,0,0,1,0],
    [0,0,0,0,0,1,0],
    [0,0,0,0,0,0,1],
    [0,0,0,0,0,0,1],
    [0,0,0,0,0,0,0],
]

acc=[0]*len(name)           # 사전 작업 개수를 등록할 배열 (진입 차수 표현)
used=[0]*len(name)          # 사전 작업이 0개 남았을 때 used를 1로 바꿔줄 예정

q = deque()
for j in range(len(name)):  # 사전 작업 개수 등록
    for i in range(len(name)):
        if arr[i][j]==1:
            acc[j]+=1

for i in range(len(name)):  # 바로 작업 착수 가능한 것들은 (진입 차수 0)
    if acc[i]==0:           # used에 1체크 하고 q에 등록
        used[i]=1
        q.append(i)

while q:
    now = q.popleft()
    print(name[now])
    for i in range(len(name)):
        if arr[now][i]==1 and used[i]==0: 
            if acc[i]==1:   # 사전 작업이 1개 남았을 때
                used[i]=1
                acc[i]-=1
                q.append(i)
            else:           # 사전 작업이 1개 이상 남았을 때
                acc[i]-=1
'''
cs
language
project
datastructure
algorithm
codingtest
to be a programmer
'''

# 인접 리스트로 그래프가 표현되어 있을 때
from collections import deque

name=['cs','language','datastructure','algorithm','project','codingtest','to be a programmer']

arr = [
    [6],
    [2,3],
    [5],
    [5],
    [6],
    [6],
    [],
]

acc=[0]*len(name)           # 사전 작업 개수를 등록할 배열 (진입 차수 표현)
used=[0]*len(name)          # 사전 작업이 0개 남았을 때 used를 1로 바꿔줄 예정

for i in range(len(arr)):   # 사전 작업 개수 등록
    for j in range(len(arr[i])):
        acc[arr[i][j]] += 1
    
q = deque()
for i in range(len(name)):  # 바로 작업 착수 가능한 것들은 (진입 차수 0)
    if acc[i]==0:           # used에 1체크 하고 q에 등록
        q.append(i)

result = []
while q:
    now = q.popleft()
    result.append(name[now])
    for i in arr[now]:
        acc[i] -= 1
        if acc[i] == 0:     # 사전 작업이 다 끝났을 때
            q.append(i)
        
print(*result, sep='\n')
'''
cs
language
project
datastructure
algorithm
codingtest
to be a programmer
'''

💡위상 정렬 활용 문제

• 백준
  • 줄 세우기
  • 작업