Skip to main content

위상 정렬

위상 정렬이란?​

위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 가장 쉬운 예로 대학교 선수과목 구조를 예로 들 수 있다. 만약 특정 수강 과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다.

이처럼 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해서 위상정렬을 사용할 수 있다.

위상정렬 여러개의 답이 존재할 수 있고, 사이클이 없는 방향그래프(DAG)에만 적용이 가능하다는 특징이 있다.

위상 정렬 수행과정​

위상정렬 알고리즘은 두가지 해결책을 낸다는 특징이 있다.

  1. 현재 그래프는 위상 정렬이 가능한지 판단한다.
  2. 위상 정렬이 가능하다면 그 결과는 무엇인지 도출한다.

또한, 위상정렬을 수행하는 알고리즘은 크게 스택과 큐방식이 존재한다. 여기서는 큐방법을 이용해 위상정렬을 구현해보도록 하겠다.

위상정렬의 수행과정은 다음과 같다.

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

위상정렬 시뮬레이션​

예제로 풀어보는 위상정렬​

이번에 풀어볼 문제는 백준의 줄 세우기 문제이다. 이 문제를 통해 위상정렬을 익혀보도록 하자.

문제​

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

입력​

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

학생들의 번호는 1번부터 N번이다.

예제 입력​

3 2

1 3

2 3

풀이​

from collections import deque

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
inDeg = [0] * (n + 1)
q = deque()
result = []

for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)  # 그래프를 만든다.
    inDeg[y] += 1       # 진입차수 세팅

for i in range(1, n + 1): # 진입차수가 0인 것 부터 큐에 넣는다.
    if inDeg[i] == 0:
        q.append(i)

while q:  # 큐를 돌면서 위상정렬 수행
    a = q.popleft()
    result.append(a)
    for x in graph[a]:
        inDeg[x] -= 1
        if inDeg[x] == 0:
            q.append(x)

print(*result)

위상정렬 시간복잡도​

위상정렬의 시간 복잡도는 O(V+E) 이다. 정점의 갯수 + 간선의 갯수만큼 소요되기 때문에 매우 빠른 알고리즘 중 하나이다.

위상정렬을 더 풀고 싶다면?​

나올 수 있는 면접 질문​

  • 위상정렬이란 무엇인가요?
  • 위상정렬 알고리즘을 설명해보세요.
  • 위상정렬의 시간복잡도는 어떻게 되나요?

참고​

기여자​


Kyun Heo
📦