[백준] 1766 문제집 (파이썬 python)

 

 

문제 링크

 

https://www.acmicpc.net/problem/1766

1766번: 문제집

 

 

문제 풀이

 

import heapq

n, m = map(int, input().split())
indegree = [0] * (n + 1)
graph = [[] for _ in range(n + 1)]

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

def topology_sort():
    result = []
    q = []
    for i in range(1, n + 1):
        if indegree[i] == 0:
            heapq.heappush(q, i)

    while q:
        now = heapq.heappop(q)
        result.append(now)
        for i in graph[now]:
            indegree[i] -= 1
            if indegree[i] == 0:
                heapq.heappush(q, i)

    for i in result:
        print(i, end=' ')

topology_sort()

 

 

노드 사이에 순서(방향성)가 존재하며, 사이클이 없는 그래프의 형태를 띄므로

위상정렬 알고리즘으로 풀이할 수 있다.

위상정렬 알고리즘은 보통 Deque를 사용하지만,

이 문제에서는 순서를 유지하되 오름차순 정렬을 하는 것을 조건으로 두고 있다.

이에 따라, Deque 대신 최솟값 정렬을 보장하는 Heapq를 사용하여 풀이했다.

 

위상정렬의 핵심은

 

1. 입력받을 때 진입차수를 1씩 증가

2. 초기 진입차수가 0인 것을 큐에 넣어 연결된 다음 노드를 찾아 진입차수를 1 감소

3. 이 때, 해당 노드의 진입차수가 0이 될 경우 다시 큐에 집어넣기

큐가 빌 때까지 2 -> 3 반복

 

이렇게 진입차수가 0인 노드들을 하나씩 빼내어

방향성에 따른 노드 순서를 출력하는 것이다.

 

사이클이 존재하면 모든 노드를 돌기 전에 큐가 비어버리므로

사이클이 없는 방향 그래프가 위상정렬의 조건이 된다.