[백준 1766] 문제집 (자바)

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

1766번: 문제집

난이도 : 골드 2

 

위상 정렬을 이용해 풀 수 있는 문제입니다.

하지만 세 가지 조건에 따라 풀어야 하는데 먼저 푸는 문제를 먼저 풀고 쉬운 문제부터 풀어야 합니다.

이 부분은 우선순위 큐를 이용하여 풀었습니다.

 

예제로 확인해보겠습니다.

4-2, 3-1 순으로 문제를 풀어야 합니다. 쉬운 문제부터 풀어야 하므로 우선순위 큐에는 3, 4가 들어갑니다.

3번을 풀고 연결된 1번 문제를 풀 수 있으니 우선순위 큐에는 1, 4가 남습니다. 1번을 풀고 4번을 풀고 연결된 2번을 풀 수 있습니다.

이처럼 link [n] == 0인 값들을 쉬운 문제(수가 작은)순으로 풀면 됩니다.

 

2020/10/02 - [문제풀이/자바] - [백준 2252] 줄 세우기 (자바)

[백준 2252] 줄 세우기 (자바)

여기서 위상정렬에 대한 자세한 설명을 볼 수 있습니다.

---

메소드

void main

조건을 관리하는 배열인 link와 연결을 관리하는 list를 선언하고 적절히 입력해줍니다.

이 문제를 풀기 위한 자료 구조인 우선순위 큐를 선언하고 link가 0인 값들을 넣어줍니다.

숫자가 작은 것부터 차례대로 꺼낸 후 연결된 값들의 link를 1 감소시키고 0인 것들을 또 우선순위 큐에 넣어주면서 문제를 풀어나갑니다.