위상 정렬(Topology Sort)

위상정렬은 순서가 정해져 있는 작업을 차례로 수행해야 할 때, 그 순서를 결정해 주기 위해 사용하는 알고리즘이다. 순서가 정해져있는 작업의 대표적인 예시는 다음과 같다.

그래프의 흐름은 '조건'으로 해석할 수 있다. 일반적으로 정처기를 취득하기 위해서는 반드시 '4학년 되기'를 만족해야하고, 4학년이 되기 위해서는 그 전에 '대학생 되기'를 만족해야 한다. 이렇게 작업의 순서가 정해져 있을 때 작업을 정확하게 정렬해주는 알고리즘이 필요할 수 있다.

위상정렬 : 대학생 되기 -> 학과 사이트 가입하기 -> 4학년 되기 -> 정보처리기사 합격하기 -> 자격 서류 제출하기 -> 졸업시험 신청하기 -> 졸업하기

위 답 말고도 다른답도 존재한다. 왜냐하면 위상 정렬은 여러개의 답이 존재할 수 있기 떄문이다. 또한 위상정렬은 DAG(Directed Acycle Graph)에만 적용 가능하다. 이는 사이클이 발생하지 않는 단 방향 그래프라는 뜻이다.

과정

1. 진입차수가 0인 정점을 큐에 삽입한다.
2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다.
3. 간선 제거 이후에 진입차수가 0이 된 정점을 큐에 삽입한다.
4. 큐가 빌 때까지 2번~3번 과정을 반복한다. 모든 원소를 방문하기 전 큐가 빈다면 사이클이 존재하는 것이고, 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과이다.

시간 복잡도

정점의 갯수 + 간선의 갯수 만큼 소요되므로 O(V+E) 이다.

Python 코드

백준 2637
위상정렬로 실행했을 때, 저장공간 잡는 부분이 어려웠다.

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
M = int(input())

l =[[]for _ in range(N+1)]
count =[[0]*(N+1) for _ in range(N+1)]
inDegree =[0]*(N+1)

# X 만드는데 중간 or 기본 Y가 K개 필요하다
for _ in range(M):
    x,y,k = map(int,input().split())
    l[y].append((x,k))
    inDegree[x] += 1

q = deque()
def topologySort():
    for _ in range(1,N+1):
        if inDegree[_] == 0:
            q.append(_)
    
    while q:
        now = q.popleft()
        for next,next_need in l[now]:
            if count[now].count(0) == N+1:
                count[next][now] += next_need
            else:
                for i in range(1,N+1):
                    count[next][i] += count[now][i] * next_need
            inDegree[next] -= 1
            if inDegree[next] == 0:
                q.append(next)

topologySort()
for x in enumerate(count[N]):
    if x[1]>0:
        print(*x)