[Baekjoon Online Judge] 백준 1766번 문제집(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 1766번 문제집

(Python)

(글쓴날 : 2020.06.17)

 

---

* Baekjoon Online Judge, 백준 1766번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 1766번 문제집

---

1) 문제

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

1766번: 문제집

---

2) 풀이 과정

* 시간 복잡도 : O(n log n)

 

1번부터 N번까지 각 번호가 난이도를 의미하는 문제들이 주어지고, 주어지는 순서를 최우선으로 하되 가능하면 난이도순으로 문제를 해결하는 순서를 구하는 문제입니다.

 

저의 경우, 위상 정렬과 우선순위 큐를 적용하였으며, Python을 사용했습니다.

우선, 주어지는 정보들을 인접 리스트로 구현하였고, 진입 차수가 0인 문제들을 최소힙 기반의 우선순위 큐에 저장한 뒤, 위상 정렬을 적용하여 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

import sys, heapq
input = sys.stdin.readline
 
 
def topologicalSort():
    for _ in range(N):
        if not hq:
            return
        
        target = heapq.heappop(hq)
        sequence.append(target)
 
        for x in adjList[target]:
            indegree[x] -= 1
 
            if not indegree[x]:
                heapq.heappush(hq, x)
 
 
N, M = map(int, input().split())
 
sequence = []
indegree = [0] * (N + 1)
adjList = [[] for _ in range(N + 1)]
 
for _ in range(M):
    A, B = map(int, input().split())
 
    indegree[B] += 1
    adjList[A].append(B)
 
hq = []
for i in range(1, N + 1):
    if not indegree[i]:
        heapq.heappush(hq, i)
 
topologicalSort()
 
print(*sequence)

---