[Python] 백준 1766 - 문제집 문제 풀이

Overview

BOJ 1766번 문제집 Python 문제 풀이
분류: Topological Sorting (위상정렬)

---

문제 페이지

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

---

풀이 코드

from sys import stdin
from collections import defaultdict
from typing import List
from heapq import heappop, heappush


def topology(n: int, indegrees: defaultdict, graph: defaultdict) -> List[int]:
    hq = []
    # indegree가 0인 노드를 찾아 heap에 삽입
    for i in range(1, n + 1):
        if indegrees[i] == 0:
            heappush(hq, i)

    res = []
    # 위상 정렬 실행
    for _ in range(n):
        node = heappop(hq)
        res.append(node)
        for neighbor in graph[node]:
            indegrees[neighbor] -= 1

            if indegrees[neighbor] == 0:
                heappush(hq, neighbor)

    return res


def main():
    def input():
        return stdin.readline().rstrip()

    n, m = map(int, input().split())
    indegrees = defaultdict(int)
    graph = defaultdict(list)

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

    print(*topology(n, indegrees, graph))


if __name__ == "__main__":
    main()

Topological Sorting을 이용하여 해결하였다.
입력을 받으면 indegrees와 graph에 각각 노드의 진입 차수(indegree)와 순서를 저장한다.
topology 함수에서는 indegree가 0인 노드를 찾아 힙에 저장하고, 위상정렬을 수행하며 정답을 구한다.