위상정렬 알고리즘

위상정렬 알고리즘이란 우선순위가 정해져있는 작업을 처리할 때, 해당 작업의 순서를 결정해주기 위한 알고리즘이다.

 

대학의 수강신청을 예를 들어보자.

과목 1, 2, 3, 4, 5가 있다.

3번 과목을 듣기 위해선 4번 과목을, 5번 과목을 듣기 위해선 1번 과목을 사전에 들을 필요가 있다.(선수과목)

 

이 경우 다음 과 같이 표현할 수 있다.

4 -> 3

1 -> 5

전체 순서를 구했을 때, 4번이 3번보다 앞에 있어야 하고, 1번이 5번보다 앞에 있어야 한다.

 

조건이 적을 경우 간단히 생각하는 것 만으로도 순서를 구할 수 있다. 위의 예시의 경우 1번과 4번을 앞에 적어주고 2, 3, 5번을 뒤에 적어주는 식으로(ex: 1 4 2 3 5) 답을 출력할 수 있다.

그러나 조건이 많아진다면 위와 같은 단순한 방법으로는 순서를 구할 수 없다.

 

4 -> 3

1 -> 5

2 -> 1

1 -> 4

2 -> 4

 

이렇게 조건이 주어질 경우 위상정렬 알고리즘을 사용해주어야 한다.

기본이 되는 구현 코드는 다음과 같다.

from collections import deque

def topo_sort():
    ans_list = []
    while q:
        ni = q.popleft()
        ans_list.append(ni)
        for i in solve_seq[ni]:
            in_degree[i] -= 1
            if in_degree[i] == 0:
                q.append(i)
    
    return ans_list

n, m = map(int, input().split())
solve_seq = [[] for _ in range(n + 1)]
in_degree = [0] * (n + 1)

# 1. 입력
for i in range(m):
    x, y = map(int, input().split())
    solve_seq[x].append(y)
    in_degree[y] += 1

# 2. 큐 생성
q = deque()

# 3. 진입차수가 0인 노드 큐에 삽입
for i in range(1, n + 1):
    if in_degree[i] == 0:
        q.append(i)

# 4. 위상정렬 알고리즘 수행
ans = topo_sort()

# 5. 해결 순서 출력
for i in ans:
	print(i, end=' ')

 

solve_seq: 해결  우선순위를 저장하는 이차원리스트.

in_degree: 진입차수를 저장하는 리스트. 간단히 말해 해당 인덱스에 해당하는 노드를 방문하기 위해 반드시 거쳐야 하는 노드의 수를 저장해둔 리스트.

 

1. 입력

x가 선수과목, y가 x를 들은 후 들어야하는 과목이다.

solve_seq의 x번째 인덱스에 해당하는 부분(x과목이 선수과목이 되는 과목이라는 의미)에 y 과목을 넣어준다.

그 후 in_degree의 y번째 인덱스에 해당하는 값을 1 올려준다. (y 과목을 듣기 위해 필요한 선수과목의 수를 체크)

 

2. 큐 생성

선입선출 구조를 활용하여 우선순위를 정리하기 위함.

 

3. 진입차수가 0인 과목(선수과목이 없는 과목)을 큐에 넣어주는 과정. 선수과목이 없는 과목이므로 시작점 역할을 함.

 

4. 위상정렬 알고리즘

큐에 있는 노드를 빼준다. 뺀 노드를 활용하여 해당 노드를 선수과목으로 가지는 과목들을 순회한다.

선수과목 역할을 하는 노드가 하나 빠졌으므로, 순회하며 in_degree 값을 1 줄여준다.

in_degree 값이 0이 되었다면 해당 시점에서의 시작점 역할을 할 수 있기 때문에, 큐에 넣어주는 과정을 거친다.

큐에 값이 없어질 때까지 반복하며, 큐에서 값을 빼주는 순서를 ans_list에 저장한다.

만약 저장된 값과 전체 노드의 수가 맞지 않다면 해당 구조는 싸이클을 갖는다고 볼 수 있으며, 싸이클을 갖는 경우 위상정렬 알고리즘을 수행할 수 없다.

싸이클을 형성하지 않는다면 저장된 ans_list를 return 해주자.

 

5. 출력