위상 정렬 알고리즘

위상 정렬 (topological sorting)

방향 그래프에서 노드의 방문 순서를 찾는 알고리즘이다.

 

우리 일상에서 접할 수 있는 위상정렬의 한 예는 수업 커리큘럼이 있다.

 

내가 나온 학교의 예를 들면

 

c프로그래밍 > 고급 c 프로그래밍 > 자료구조 > 알고리즘

순으로 수강을 할 수있다. 즉 앞의 과목들은 선수과목이 되는것이다.

 

위 순서를 어기고선 수강을 할 수 없는데 이러한 순서를 찾는것이 위상정렬 알고리즘이다.

 

---

 

위상 정렬 알고리즘을 사용하기 위해선 사이클이 없는 방향 그래프여야 한다.

 

즉 A > B > C > A 로 돌아가는 방향을 갖는 그래프이면 안된다.

 

알고리즘은 간단하다.

 

1. 1차원 배열로 그래프를 구현한다.
2. 진입차수가 0인 그래프를 큐에 넣는다.
3. 큐를 빼면서 해당 노드의 다음 노드의 진입차수를 -1 한다.
4. 2~3 반복

아래의 그래프 이미지는 이것이 코딩테스트다[이코테] 교재

위의 그래프를 정리하자면

<그래프>

1	2	3	4	5	6	7
2, 5	3, 6	4	7	6	4

 

<진입 차수>

1	2	3	4	5	6	7
0	1	1	2	1	2	1

 

 

위와 같이 정리할 수 있다. 이 두 개의 배열을 가지고 문제를 풀 수 있다.

 

여기서 진입차수가 0인 1번노드가 먼저 큐에 삽입된다.

 

 

---

 

이후 1번과 연결된 2, 5번 노드의 진입차수를 -1 하고 0이면 큐에 삽입한다.

 

 

---

 

2와 연결된 3, 6

5와 연결된 6을 pop하고 해당 진입차수를 -1 해준다.

 

---

위의 과정을 반복하여

 

모든 노드에 방문하고 큐가 비게된다면 위상정렬 종료

 

방문 순서는 맨처음 진입차수가 0인 순서대로

 

1 > 2 > 5 > 3 > 6 > 4 > 7 이된다.

 

import sys
# 입력 빠르게 받기 위해 sys.stdin.readline 사용
input = sys.stdin.readline

# n: 노드의 개수, m: 간선의 개수
n, m = map(int, input().split())
# 각 노드에 연결된 간선 정보를 저장할 리스트
graph = [[] for _ in range(n+1)]
# 각 노드의 진입 차수를 저장할 리스트
degree = [0] * (n+1)
# 모든 간선 정보를 입력 받아 그래프를 구성하고 진입 차수를 업데이트
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    degree[b] += 1
    
from collections import deque

# 진입 차수가 0인 노드를 찾아 큐에 삽입
q = deque()
for i in range(1, n+1):
    if degree[i] == 0:
        q.append(i)
        
# 큐가 빌 때까지 반복
while q:
    # 큐에서 원소를 꺼내 출력
    node = q.popleft()
    print(node, end=' ')
    # 해당 노드에 연결된 노드들의 진입차수를 감소시키고, 진입 차수가 0이 되면 큐에 삽입
    for i in graph[node]:
        degree[i] -= 1
        if degree[i] == 0:
            q.append(i)