https://www.acmicpc.net/problem/1766
1766번: 문제집
첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주
www.acmicpc.net
import sys
from collections import deque
import heapq
n,m = map(int,sys.stdin.readline().split())
indegree = [0] * (n+1)
graph =[[] for _ in range(n+1)]
for _ in range(m):
a, b = map(int,sys.stdin.readline().split())
indegree[b] += 1
graph[a].append(b)
def topology_sort():
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)
for i in graph[now]:
indegree[i] -= 1
if indegree[i] ==0:
heapq.heappush(q,i)
for i in result:
print(i, end= " ")
topology_sort()이 문제는 우선순위 큐
다익스트라에서 많이 사용하는 큐를 같이 사용해야 풀린다
위상 정렬에 우선 순위 큐까지
문제의 조건에 맞게 풀면된다.
참고하면 좋은 문제
https://zoozoozoo.tistory.com/412
[백준] 14500번 줄 세우기(위상 정렬) - 파이썬
https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가..
zoozoozoo.tistory.com
https://zoozoozoo.tistory.com/411
위상 정렬
위상 정렬은 정렬 알고리즘의 일종이다. 위상 정렬은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 조금 더 이론적으로 설명하자면, 위상 정렬이
zoozoozoo.tistory.com
개념
https://zoozoozoo.tistory.com/415
[백준] 1916번 최소비용 구하기 - 파이썬
https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지..
zoozoozoo.tistory.com
'알고리즘 공부 > 위상정렬' 카테고리의 다른 글
| [백준] 14500번 줄 세우기(위상 정렬) - 파이썬 (0) | 2022.04.12 |
|---|---|
| 위상 정렬 (0) | 2022.04.12 |