백준 1766 문제집

백준 1766 문제집

원문보기

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

방법론 : 위상정렬 + 우선순위 큐

이 문제는 위상정렬 문제이지만, 스페셜 저지가 아니였다. 즉 정답이 하나라는 이야기인데, 어떻게 이런 조건을 가지게 되었는지 살펴보자.

문제를 보면 n개의 문제와 m개의 간선 정보가 나온다.

"문제" (실제 문제와 문제의 예제에 나오는 문제와 헷갈리지 않게 쌍따옴표로 강조했다.) 의 난이도가 낮는 것부터 우선순위를 두고싶다고 한다.

그러면서도, 동일한 난이도가 없기 때문에 스페설 져지 문제가 아닌 답이 하나로 결정될수 있었다. 

큐에서 꺼낼땐 난이도 낮은것부터 꺼내었다.

C++의 STL priority_queue 자료구조를 이용했다.

소스보기

https://github.com/ingyeoking13/algorithm/blob/master/bj/p1000/1766.cc