#35 위상 정렬(Topological Sorting)
위상 정렬의 개념과 이를 활용하여 해결할 수 있는 문제를 알아본다.
1. 위상 정렬(Topological Sorting)
위상 정렬은 간단히 말하자면 순서를 가진 항목들을 줄 세우는 정렬방식이다. 예를 들어 1은 반드시 3보다 앞에 오고
2는 반드시 4보다 앞에 온다고 해보자, 이 때, [1, 2, 3, 4]를 위상 정렬한 결과는 [1, 3, 2, 4], [1, 2, 3, 4], [2, 4, 1, 3],
[2, 1, 4, 3] 모두가 될 수 있다. 즉, 주어진 항목간의 순서를 유지하는 것을 전제로 정렬을 수행하는 것이다. 주로 어떤
작업들을 수행되어야 할 순서에 따라 배치하기 위해 사용되는 알고리즘이다. 정렬의 대상은 기준이 될 명확한 순서가
존재해야 하기 때문에 당연히 방향성을 가졌으며 사이클이 존재하지 않는 그래프의 형태로 나타낼 수 있어야 한다.
2. 줄 세우기(https://www.acmicpc.net/problem/2252) - 위상 정렬의 구현
학생의 수(노드의 갯수)와 학생들의 키를 비교한 결과(간선)가 주어졌을 때 학생들을 키순서로 줄 세우는 문제
위상 정렬의 구현을 연습할 수 있는 문제이다. 구현의 절차는 다음과 같다.
① 우선 위상 정렬을 위해 필요한 것은 그래프와 진입 차수 테이블이다. 주어진 노드의 갯수와 간선을 이용하여
이 두 가지를 먼저 구해야한다. 노드 X의 진입 차수는 X로 직접 올 수 있는 길을 가진 노드의 갯수를 의미한다.
② 진입 차수가 0인 노드를 순서에 상관없이 모두 큐에 집어넣는다.
③ 큐에서 노드를 꺼내서 해당 노드로부터 뻗은 간선을 모두 제거하고 진입 차수 테이블을 갱신한다.
④ ②, ③ 작업을 큐가 빌 때 까지 반복한다.
⑤ 작업이 끝났을 때, 큐에서 노드를 꺼낸 순서가 곧 위상 정렬된 순서가 된다.
이를 구현한 코드는 다음과 같다.
import sys
input = sys.stdin.readline
def sol2252():
# 학생의 수 n, 비교 결과의 수 m
n, m = map(int, input().split())
# 학생을 노드로, 비교 결과를 간선으로 하여 그래프로 표현
# 각 노드(학생)의 진입 차수 테이블을 생성
g = [[] for _ in range(n + 1)]
degree = [0] * (n + 1)
for _ in range(m):
a, b = map(int, input().split())
degree[b] += 1
g[a].append(b)
# 진입 차수가 0인 모든 노드를 큐에 삽입
q = [i for i in range(1, n + 1) if not degree[i]]
# 정렬 결과 리스트
answer = []
# 큐가 빌 때 까지
while q:
nq = []
# 큐에서 노드를 하나씩 꺼내 정렬 결과 리스트 answer 에 삽입
# 해당 노드로부터 뻗은 간선을 제거하고 진입 차수를 갱신
# 그 결과 진입 차수가 0이 된 노드를 모두 큐에 삽입
for num in q:
answer.append(num)
for child in g[num]:
degree[child] -= 1
if degree[child] == 0:
nq.append(child)
q = nq
# 출력 형식에 맞춰 정렬 결과를 반환
return ' '.join(map(str, answer))
3. 최종 순위(https://www.acmicpc.net/problem/3665)
작년의 팀들의 순위, 올해 상대적 순위가 변경된 팀의 순서쌍이 주어졌을 때, 올해 팀들의 순위를 구하는 문제.
역시 위상 정렬을 사용하여 해결 가능하지만 작년의 순위와 변경된 순서쌍만으로 순위를 추측해야한다. 주의할 점은
주어진 순서쌍의 순서는 실제로 변경된 순위와는 관계가 없다는 것이다. 예를들어, 작년의 순위가 1, 2 였을 때,
순서쌍이 1, 2로 주어지든 2, 1로 주어지든 최종 순위는 2, 1이 되어야 한다.
문제를 해결하는 절차는 다음과 같다.
① 기존 순위를 토대로 간선을 생성한다. 예를들어 기존 순위가 5 4 3 2 1 일 경우, 간선은
(5, 4), (5, 3), (5, 2), (5, 1), (4, 3), (4, 2), (4, 1), (3, 2), (3, 1), (2, 1) 이 된다.
② 생성한 간선으로 그래프와 진입 차수 테이블을 생성한다.
③ 순위가 변경된 팀의 순서쌍에서 더 낮은 순위였던 쪽을 a, 더 높은 순위였던 쪽을 b로 하여 그래프와
진입 차수 테이블을 수정한다.
④ 그래프에 대해 위상 정렬을 수행한다.
⑤ 위상정렬의 수행한 결과 리스트의 길이가 총 노드의 갯수에 미치지 못할 경우 그래프에 사이클이 존재한다는
의미이기 때문에 데이터에 일관성이 없어 순위를 정할 수 없는 경우에 속하므로 IMPOSSIBLE을 출력한다
⑥ 그렇지 않다면 정상적으로 위상 정렬이 완료된 것이기 때문에 정렬 결과를 출력한다.
이를 구현한 코드는 다음과 같다.
import sys
input = sys.stdin.readline
def sol3665():
# 케이스별 정렬 결과 리스트
answer = []
for t in range(int(input())):
# 팀의 수(노드의 수)
n = int(input())
# 작년 순위에 따라 그래프와 차수 테이블 생성
g = [set() for _ in range(n + 1)]
degree = [0] * (n + 1)
teams = list(map(int, input().split()))
for i in range(n):
a = teams[i]
for j in range(i + 1, n):
b = teams[j]
g[a].add(b)
degree[b] += 1
# 변경된 순위에 따라 그래프와 차수 테이블 수정
m = int(input())
for _ in range(m):
a, b = map(int, input().split())
# 보다 낮은 순위였던 쪽이 a가 되게 한다
if a not in g[b]:
a, b = b, a
g[b].discard(a)
g[a].add(b)
degree[a] -= 1
degree[b] += 1
# 정렬 결과
res = []
# 위상 정렬 수행
q = [i for i in range(1, n + 1) if not degree[i]]
while q:
nq = []
for num in q:
res.append(num)
for child in g[num]:
degree[child] -= 1
if not degree[child]:
nq.append(child)
q = nq
# 사이클이 발견된 경우 -> 일관성이 없어 정렬이 불가능한 경우
if len(res) != n:
answer.append('IMPOSSIBLE')
# 정렬이 정상적으로 수행된 경우
else:
answer.append(' '.join(map(str, res)))
# 출력 형식에 맞춰 정렬 결과 반환
return '\n'.join(answer)
4. 문제집(https://www.acmicpc.net/problem/1766)
문제집의 1~N까지의 문제를 풀 순서를 다음 세가지 조건에 따라 정하는 문제
1. N개의 문제는 모두 풀어야한다
2. 먼저 푸는 것이 좋은 문제가 있는 문제는 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
3. 가능하면 쉬운 문제부터 풀어야 한다. (문제 번호가 낮을수록 난이도가 낮다)
순서를 지켜야한다는 점에서 알 수 있듯이 위상정렬을 사용하여 해결 가능한 문제이다. 다만 같은 단계에서
진입 차수가 0이라면 순서가 상관없었던 기존의 위상정렬로는 3번 조건을 만족시킬 수 없다. 여기서는
기존의 큐를 heapq 로 대체하는 것으로 문제를 해결할 수 있다. 구현은 다음과 같다.
import sys
from heapq import heappush, heappop, heapify
input = sys.stdin.readline
def sol1766():
# 문제의 갯수 n, 먼저 푸는게 좋은 문제의 정보의 갯수 m
n, m = map(int, input().split())
# 그래프, 진입 차수 테이블 생성
g = [[] for _ in range(n + 1)]
degree = [0] * (n + 1)
for _ in range(m):
a, b = map(int, input().split())
g[a].append(b)
degree[b] += 1
# 최초에 진입 차수가 0인 노드(문제)를 큐에 담는다
q = [i for i in range(1, n + 1) if not degree[i]]
# 큐를 heapq로 변환
# Python의 heapq는 기본적으로 최소 힙이기 때문에
# 더 작은 숫자, 즉 더 쉬운 문제부터 뽑게된다.
heapify(q)
# 정렬 결과 리스트
answer = []
# 위상 정렬 실행
# 기존의 방식과 같지만 큐에서 값을 꺼내고 다시 넣는 동작을
# heappop 과 heappush를 사용하여 수행한다.
# 이것으로 매번 가능하면 가장 쉬운 문제를 해결하는 3번 조건을 만족시킨다.
while q:
cur = heappop(q)
answer.append(cur)
for c in g[cur]:
degree[c] -= 1
if not degree[c]:
heappush(q, c)
# 출력 조건에 따라 정답 리스트 반환
return ' '.join(map(str, answer))heap을 사용하면 항상 정렬된 것과 마찬가지인 상태를 유지할 수 있다는 점만 떠올리면 쉽게 해결할 수 있는 문제였다.
위상정렬의 구현은 다음에 알아볼 dfs를 사용한 구현이 보다 간단하지만 큐를 사용한 구현이 풀이에 적합한 경우도 있기 때문에 두 방법 모두 숙지해둘 필요가 있다.