[Algorithm] 백준 2252 : 줄 세우기

문제
https://www.acmicpc.net/problem/2252
풀이
https://github.com/nowChae/algorithm/blob/master/%EB%B0%B1%EC%A4%80/Gold/2252.%E2%80%85%EC%A4%84%E2%80%85%EC%84%B8%EC%9A%B0%EA%B8%B0/%EC%A4%84%E2%80%85%EC%84%B8%EC%9A%B0%EA%B8%B0.py

위상 정렬을 사용하는 문제였다. 위상 정렬이란 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 대학의 선수과목(prerequisite) 구조를 위상 정렬의 예로 들 수 있다.

위상 정렬 알고리즘을 사용하면 쉽게 풀 수 있는 문제였다. 진입차수가 0인 정점을 큐에 넣고, 큐에서 값을 빼면서 연결된 모든 간선을 제거한다. 만약 제거한 간선으로 인해 진입차수가 0이 된 정점이 있다면 이 정점은 큐에 넣는다. 이 과정을 큐가 빌 때까지 반복해주면 결과를 얻을 수 있다.

이 문제를 풀기 전에 위상 정렬에 대하여 찾아보았고, 위상정렬을 직접적으로 이용한 문제라는 것을 "순서대로 정렬"과 "답이 여러 가지인 경우"라는 부분에서 알 수 있었다.

< 풀이 코드 >

#위상 정렬
import sys
input = sys.stdin.readline


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

graph = [[] for _ in range(N+1)]
connect = [0] * (N+1)

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    connect[b] += 1

unvisited_count = N

queue = []

# 들어오는 선이 없는 값들을 큐에 넣음
for i in range(1, N+1):
    if connect[i] == 0:
        queue.append(i)

while queue:
    r = queue.pop(0)
    print(r)

    for i in graph[r]:
        #연결된 선을 제거
        connect[i] -= 1
        #들어오는 선이 없는 경우에만 큐에 넣음
        if connect[i] == 0:
            queue.append(i)
            unvisited_count -= 1

    if unvisited_count == 0:
        break