[복기] 2252번: 줄 세우기

문제

백준 2252번: 줄 세우기

알고리즘 분류

• 위상정렬

나의 풀이

일반적인 정렬로는 풀지 못한다. 위상 정렬이라는 특수한 정렬을 써야한다. 위상정렬의 개념만 이해하면 바로 풀 수 있다. 자신보다 키가 작은 사람이 없는 학생을 큐에 담고, 큐에 대해 BFS를 수행한다. 큐에서 꺼낼 때마다 줄을 세운다. 자신보다 키가 작은 사람이 있는 학생은 그 학생이 줄에 세워지기 전까지는 큐에 들어갈 수 없다. 자신보다 키가 작은 학생이 줄에 세워지면 그 학생에 대한 의존성이 없어진 것이므로, 이제 큐에 들어갈 수 있다. 이러한 과정을 반복하여 학생 간의 키 우선순위만으로 정렬한다. 우선순위 정보가 없는 학생들은 마지막에 체크하여 줄에 세워준다.

 

처음엔 큐를 그냥 list로 두었는데 시간이 5000ms가 나왔다. 그런데 deque 모듈을 쓰니 232ms까지 줄었다. 역시 모듈이 좋긴 좋다. 시간차이는 아마 list의 append()는 메모리 재할당을 일으키고, 큐에서 pop(0) 하는 것도 메모리 재할당을 일으키니 이때문에 시간초과가 일어났으리라 추측한다. deque 모듈은 queue 연산에 최적화된 자료구조를 가지고 있을테니 속도가 아주 빠르리라.

코드

from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
out_node = [[] for _ in range(n)] 
in_degree = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    in_degree[b-1] += 1
    out_node[a-1].append(b-1)

visited = [False] * n
queue = deque()
answer = []

for i in range(n):
    if in_degree[i] == 0:
        queue.append(i)
        visited[i] = True

while queue:
    cur = queue.popleft()
    answer.append(cur+1)

    for out in out_node[cur]:
        if not visited[out]:
            in_degree[out] -= 1

            if in_degree[out] == 0:
                queue.append(out)
                visited[out] = True

print(*answer)