[Python Algorithm] 백준 문제집 - 1766
풀이 과정
위상정렬을 사용해서 푸는 문제이다.
주의해야 할 점은 각 노드에서 우선순위가 있기 때문에 일반 큐가 아닌 우선순위 큐를 사용하여 구현해야한다.
우선순위 큐를 사용한다는 아이디어만 생각해내면 정말 편하게 풀 수 있는 문제 !
최종 코드
from heapq import heappop, heappush
N, M = map(int, input().split(' '))
graph = [[] for _ in range(N + 1)]
indegree = [0 for _ in range(N + 1)]
for _ in range(M):
a, b = map(int, input().split(' '))
graph[a].append(b)
indegree[b] += 1
q = []
for i in range(1, N + 1):
if indegree[i] == 0:
heappush(q, i)
while q:
problem = heappop(q)
print(problem, end=' ')
for p in graph[problem]:
indegree[p] -= 1
if indegree[p] == 0:
heappush(q, p)
결과
Link
Author And Source
이 문제에 관하여([Python Algorithm] 백준 문제집 - 1766), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hancihu/Python-Algorithm-백준-문제집-1766저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)