[ 백준 ][ 골드2 ] 1766번 - 문제집 ( 파이썬 )

링크 : https://www.acmicpc.net/problem/1766

1766번: 문제집

 

문제

---

코드

---

import heapq
import sys
input = sys.stdin.readline

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

first = [[] for _ in range(n+1)]
link = [0 for _ in range(n+1)]

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

hq = []
for i in range(1,n+1):
    if link[i] == 0:
        heapq.heappush(hq,i)
while hq:
    node = heapq.heappop(hq)
    print(node,end = " ")
    for x in first[node]:
        link[x] -= 1
        if link[x] == 0:
            heapq.heappush(hq,x)

 

풀이

---

대표적인 위상정렬에 작은 변화를 준 변형문제이다.

 

내가 생각하는 위상정렬은 다음과 같다.

다른 참고자료 없이 내 생각 그대로 적었기 때문에 오류가 있을 수는 있다.

어떤 노드를 방문하기 전 반드시 방문해야 하는 선순위 노드가 있을 때, 선순위 노드를 방문처리하며 후순위 노드들의 값을 갱신해가며 먼저 방문해야 할 노드들이 사라진 노드들을 다시 방문하는 방법

이 문제에서 추가로 요구하는 조건은 '가능하면 쉬운 문제부터 풀어야 한다' 이다.

가능하면 쉬운 문제라는 것은 문제에서 번호가 낮은 순이기 때문에 3번 조건을 해결하기 위해서 우선순위 큐를 사용했다.

 

| 위상정렬 + 우선순위큐 |

• 선순위 노드를 인덱스로 두고 후순위 노드들을 저장하는 배열 first와 선순위 노드의 개수들을 저장한 link배열을 만든다.
• 정보들을 모두 배열에 넣는다.
• link배열을 탐색하면서 선순위 노드가 없는 노드들을 우선순위큐에 넣는다.
• 우선순위큐에 넣으면 모두 선순위 노드가 없는 노드들 중 가장 작은 수가 먼저 나오기 때문에 3번 조건이 만족된다.
• 우선순위 큐에서 노드를 꺼낼 때마다 그 노드를 선순위로 하는 모든 노드의 link값을 줄이고 0이 되면 다시 우선순위 큐에 넣어준다.