BaekJoon 1766번 : 문제집 (python)

📝 BaekJoon 1766번 : 문제집 (G2 48.980%)

---

🔎 문제집 문제

---

📌 아이디어

이전에 풀었던 문제와 비슷하게 위상정렬과 우선순위큐 힙 자료구조를 이용하여 사전순으로 정렬을 해준다.

---

💭 풀이

• 위상정렬을 위해 각 노드들의 진입차수를 계산해주고 진입차수가 0인 노드들을 q에 먼저 넣어준다. 이때 deque()자료구조를 사용하지 않고 heapq 자료구조를 사용하여 먼저 들어온 노드가 아닌 사전순으로 작은 변수 먼저 처리를 해준다.

---

💻 코드

import heapq, sys
input = sys.stdin.readline

n, m = map(int,input().split())

node = [[] for _ in range(n+1)]
indegree = [0]*(n+1)

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

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

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

print(*result)

---