백준 / 문제집 / 1766번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 문제집 / 1766번 (골드 2단계)

문제 사이트: https://www.acmicpc.net/problem/1766

 

문제 설명

---

나의 풀이

import heapq

# 문제 조건: 위상 정렬, 우선순위 큐(힙)
# n은 문제의 수 m은 먼저 푸는 것이 좋은 문제에 대한 정보의 개수
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 toplogy_sort():
    result = []
    # 힙 배열
    heap = []

    for i in range(1, n + 1):
        if indegree[i] == 0:
            heapq.heappush(heap, i)
    
    while heap:
        current = heapq.heappop(heap)
        result.append(current)
        for i in graph[current]:
            indegree[i] -= 1
            if indegree[i] == 0:
                heapq.heappush(heap, i)
    
    for i in result:
        print(i, end = ' ')

toplogy_sort()

요즘 코테를 풀 때 문제 볼 때 시간제한, 메모리 제한, 문제 유형을 먼저 확인을 하고 풀게 되는 버릇이 생겼다. 그래서 문제를 보면 이건 이 유형으로 풀어야겠다는 생각 밖에 안 든다. 아무튼 이 문제는 위상정렬 + 힙을 사용하는 문제였다.

---

※ 알아야 할 것

https://dmaolon00.tistory.com/entry/AlgorithmPython-위상-정렬Topology-Sort란

[Algorithm/Python] 위상 정렬(Topology Sort)란?

https://newkimjiwon.tistory.com/179

[자료구조] 힙(Heap)