[Baekjoon 2252 / python / 골드3] 줄 세우기

from collections import deque

import sys

input = sys.stdin.readline

N, E = map(int, input().split())  # 노드, 간선 입력받기

indegree = [0 for _ in range(N + 1)]  # 진입차수 저장할 리스트

graph = [[] for _ in range(N + 1)]  # 연결정보 저장할 리스트

for _ in range(E):  # 연결정보 입력받기

    root, edge = map(int, input().split())

    graph[root].append(edge)

    indegree[edge] += 1  # 진입차수 추가하기

def solve():

    queue = deque()  # 덱 사용

    result = []

    for i in range(1, N + 1):  # 진입차수가 0인 노드를 큐에 삽입

        if indegree[i] == 0:

            queue.append(i)

   

    while queue:  # 큐에서 노드 꺼내기, 결과 리스트에 담기 (  큐에서 꺼내진 순서대로 위상 순서 )

        here = queue.popleft()

        result.append(here)

        for i in graph[here]:  # 현재 노드에 연결된 간선 끊기

            indegree[i] -= 1

            if indegree[i] == 0:  # 끊었는데 진입차수가 0이면 큐에 삽입한다

                queue.append(i)

   

    return result

result = solve()

for re in result:  # 결과 출력

    print(re, end=' ')

 

위상 정렬이 사용된 문제이다. 난이도는 골드3 이긴 한데, 위상정렬만 이해하고 있으면 솔직히 쉬운 문제다.

물론 위상정렬을 알려면 그래프, 트리, DFS/BFS등을 알 필요가 있기 때문에 아무것도 모르는 상태라면 어려운 문제가 맞다.

 

위상 정렬은 사이클이 없는 방향 그래프에서, 진입차수가 0인 노드부터 시작해 방향성을 유지하며 노드들을 순서대로 나열하는 알고리즘이다. 이렇게 나온 순서는 위상 순서라고 한다.

위상 정렬의 특성 상 답이 여러 개일 수가 있어서 테스트 케이스와 답이 다를 수 있다. 그냥 쫄지 말고 제출해 보면 된다.

 

난 위상 정렬은 처음 해 봤는데 BFS와 매우 흡사해서 무난하게 풀 수 있었다.