[Algorithm] 위상 정렬

위상 정렬

위상 정렬은 순서가 정해져 있는 작업을 차례로 수행해야 할 때, 순서를 결정해주는 알고리즘

DAG(Directed Acyclic Graph)그래프여야 함. 방향성이 있고, 사이클이 없는 그래프

위상 정렬의 시간 복잡도는 O(V + E)로 문제를 해결할 수 있음.

힙 자료구조와 함께 적용하면 쉽게 문제를 풀 수 있음.

 

 

위상정렬 알고리즘 순서

1) 진입 차수(Indegree, 자기 자신으로 오는 간선을 의미)가 0인 정점을 큐에 삽입한다.

2) 큐에 원소를 꺼내 해당 원소와 간선을 제거한다.

3) 제거 이후에 진입 차수가 0이 된 정점을 큐에 삽입한다.

4) 큐가 빌 때까지 2) ~ 3) 과정을 반복한다.

 

* 사이클이 존재하면 진입차수가 0인 정점을 찾을 수 없기때문에 위상 정렬 적용 불가. 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것

* 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과이다.

 

위상 정렬 예시 문제

BOJ 1766번 문제집

https://www.acmicpc.net/problem/1766

 

<풀이 코드>

import heapq

n, m = map(int, input().split())
# 각 노드에 연결되 간선 정보를 담기 위한 연결 리스트 초기화
array = [[] for i in range(n + 1)]
# 모든 노드에 대한 진입차수는 0으로 초기화
indegree = [0] * (n + 1)

heap = []
result = []

# 방향 그래프의 모든 간선 정보를 입력받기
for _ in range(m):
    x, y = map(int, input().split())
    # 정점 A에서 B로 이동 가능
    array[x].append(y)
    # 진입 차수를 1 증가
    indegree[y] += 1

# 진입 차수가 0인 노드를 큐에 삽입
for i in range(1, n + 1):
    if indegree[i] == 0:
        heapq.heappush(heap, i)

# 큐가 빌 때까지 반복
while heap:
	# 큐에서 가장 작은 원소를 꺼냄
    data = heapq.heappop(heap)
    result.append(data)
    # 해당 원소와 연결된 노드 제거
    for y in array[data]:
        indegree[y] -= 1
        # 제거 이후에 진입 차수가 0이 된 정점을 큐에 삽입
        if indegree[y] == 0:
            heapq.heappush(heap, y)

for i in result:
    print(i, end=' ')