[백준][위상정렬] 줄세우기 : 2252 Python

줄 세우기 문제이다. 백준의 키순서와 비슷하다는 느낌이었지만 백준의 키순서 문제는 자신의 순서를 정확히 알 수 있는 사람의 수를 묻는 문제였고, 순서를 정렬(정확하지 않는 사람은 임의로)한다는 점에서 차이가 있었다.

이 차이에 의하여 키순서문제는 플로이드 와샬이나 dfs를 통해 푸는 문제가 되었고, 이 문제는 위상 정렬을 통해 푸는 문제가 되었다.

위상 정렬은 진입 차수가 낮은 노드들 순으로 정렬할 때 활용하는 알고리즘이며 일상생활에서도 우리가 흔히 쓰고 있는 알고리즘이다.

대표적으로 대학교의 수강커리큘럼을 볼 때 우리가 무의식적으로 많이 사용하고 있는데 어떤 한 과목을 듣기 위해서 선수과목이 있고, 그 과목의 또 선수과목이 있다. 우리는 이를 보기 쉽게 하기 위해 선수과목의 수준이 낮은 것부터 정렬하여 커리큘럼을 본다.

이를 위상정렬에 대입하면 진입 차수가 낮은(선수과목이 없거나 수준이 낮은) 노드부터 정렬하는 과정인 것이다.

A과목의 선수과목이 B이고 B과목의 선수과목은 C, C과목의 선수과목이 A인 경우는 없다. 즉, 위상 정렬은 사이클이 없고 방향성만 존재하는 그래프에서만 가능하다

마지막으로 위상정렬을 이 문제로 대입할 수 있다. 키를 비교했을 때 A <B, B <C 라면 A의 진입 차수(A보다 키가 작은 사람)는 0, B와 C의 진입 차수는 1이 된다. 결국 진입 차수가 0인 A를 먼저 자료구조에 저장하고 A가 사라져서 진입 차수가 0이 된 B 가 그다음, 마지막으로 C가 정답에 저장된다.

이를 코드로 나타내면 아래와 같다.

from sys import stdin
from collections import deque

input = stdin.readline

N, M = map(int,input().split())

arr = [[] for _ in range(N+1)] # 방향
inD = [0] * (N+1) # 진입차수
Q = deque()
answer = []

# 진입차수와 방향 기록
for _ in range(M):
    s, t = map(int,input().split())
    arr[s].append(t)
    inD[t] += 1

# 진입차수가 0인 사람들을 Q에 저장
for i in range(1, N+1):
    if not inD[i]:
        Q.append(i) # 진입차수가 0인것 : 키가 작은 사람들


# 진입차수가 0인 사람들을 제거하면서, 이 사람들이 제거되면서 진입차수가 0이 된사람 Q에 저장
while Q:
    tmp = Q.popleft()
    answer.append(tmp)
    for i in arr[tmp]:
        inD[i] -= 1
        if inD[i] == 0:
            Q.append(i)

print(*answer)

위상정렬이 잘 이해가 안 됐었는데 위키백과의 예시(수강 커리큘럼)를 보니 확실히 이해가 되는 것 같다.

위상 정렬에 대해 잘 정리해둔 블로그들이 많았는데 그 글들을 보면 도움이 많이 될 것 같다.

문제 출처 : 백준 https://www.acmicpc.net/problem/2252

2252번: 줄 세우기