백준(1766) - 문제집 Python

백준(1766) - 문제집

문제풀이: 그래프, 파이썬

해결방법

위상정렬 알고리즘을 사용하면 되는데, 문제 조건에 가능하면 쉬운 문제부터 풀어야 한다고 했으므로 우선순위 큐를 활욯하면 된다.

예시)

4 2
4 2
3 1

import heapq
import sys
input = sys.stdin.readline

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():
    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)
        graph[now].sort()
        for i in graph[now]:
            indegree[i] -= 1
            if indegree[i] == 0:
                heapq.heappush(q, i)

    return result

result = topology()
for res in result:
    print(res, end=" ")