[백준(BOJ)] 1766번 : 문제집 - PYTHON[파이썬]

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

1766번: 문제집

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그래프 이론
• 자료 구조
• 우선순위 큐
• 위상 정렬

 

---

 

⊙ 문제 접근 과정

 

기존의 위상 정렬에 플러스 알파가 필요했다.

그 플러스 알파는 추가되는 큐에 대해 오름차순 정렬로 입력해줘야한다.

 

위상 정렬의 특징 중 하나, 위상 정렬에서는 여러 가지 답이 존재할 수 있다.

 

이 문제에서는 아니다. 가장 난이도가 쉬운 순서대로 풀어야 한다는 조건이 있다.

 

때문에 힙큐와 위상 정렬을 혼합하여 사용하면 문제를 쉽게 풀 수 있다.

 

 

 

---

 

⊙ 문제 풀이

 

import sys
import heapq

input = sys.stdin.readline

N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
indegree = [0] * (N+1)

for i in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)
    indegree[y]+=1

def topo():
    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)
        
    print(*result)

topo()

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!