[백준] 2252번: 줄 세우기

문제

백준 - 2252번: 줄 세우기

분석

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 만드는 문제이다.

문제를 딱 봤을 때 처음 보는 유형이라는 느낌이 들어 알고리즘 유형 확인 버튼을 바로 눌렀다.
위상정렬이라는 키워드를 보고 먼저 인터넷에 개념을 공부하고 코드에 적용해보려했다.
래퍼런스

방법

1. 순서가 정해진 것들로 그래프와 차수 정보(indegree)를 채운다.
2. 큐에 차수가 0인 것들을 넣는다.
3. 차수가 0인 노드를 결과에 넣고, 그 노드와 연결된 모든 것들을 끊으면서 차수 정보를 갱신한다.
   그 과정에서 차수가 0이 된 노드는 큐에 넣는다.

이 방법은 위상정렬이 보장된 경우에 가능하다.
N개의 노드를 다 탐색하기 전에 큐가 비어버리면 사이클이 발생한 경우다. 사이클이 있으면 위상정렬이 불가능하다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

from collections import deque
n, m = map(int, input().split())
degree = [0]*(n+1)
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    degree[b] += 1

result = []
q = deque()
for i in range(1, n+1):
    if degree[i] == 0:
        q.append(i)

for i in range(1, n+1):
    x = q.popleft()
    result.append(x)
    while graph[x]:
        y = graph[x].pop()
        degree[y] -= 1
        if degree[y] == 0:
            q.append(y)

print(*result)

끝으로..

위상정렬에 대해 공부하고 적용해 볼 수 있는 문제였다.