공부 자료/알고리즘
(Python/파이썬) 백준 1766번 - 문제집
뚜루뚜루세니
2021. 9. 14. 21:34
728x90
문제출처: https://www.acmicpc.net/problem/1766
1766번: 문제집
첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주
www.acmicpc.net
1. 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
# 위상정렬 알고리즘
# 진입차수가 0인 정점 큐에 삽입
# 큐에서 원소 꺼내 원소 간선 제거
# 제거 이후 진입차수가 0이된 정점 큐 삽입
# 큐가 빌 때까지 반복
import heapq
#파이썬 힙 자료구조
#최소 힙 형태로 정렬
n, m = map(int, input().split())
graph=[[] for _ in range(n+1)]
inDegree=[0 for _ in range(n+1)]
q=[]
#문제 순서
for _ in range(m):
a,b=map(int,input().split())
graph[a].append(b)
inDegree[b]+=1
#진입차수가 0이면 큐에 넣기
for i in range(1,n+1):
if inDegree[i]==0:
heapq.heappush(q,i)
#i를 q에 추가
#위상정렬
ans=[]
while q:
a=heapq.heappop(q)#힙에서 가장 작은 원소 pop = 최소 힙 사용
ans.append(a)
for i in graph[a]:
inDegree[i]-=1
if inDegree[i]==0:
heapq.heappush(q,i) #q리스트에 i추가
print(*ans)
|
cs |
2. 해결과정
위상정렬 알고리즘을 사용해서 풀어주면 된다. 문제 조건에서 가능한 쉬운 문제 부터 풀어야 한다고 명시되어 있기 때문에 힙을 이용해서 우선 순위 큐를 사용해서 시간을 줄여줬다.
728x90