티스토리 뷰
https://www.acmicpc.net/problem/1766
1766번: 문제집
첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주
www.acmicpc.net
난이도 : 골드 2
위상 정렬을 이용해 풀 수 있는 문제입니다.
하지만 세 가지 조건에 따라 풀어야 하는데 먼저 푸는 문제를 먼저 풀고 쉬운 문제부터 풀어야 합니다.
이 부분은 우선순위 큐를 이용하여 풀었습니다.
예제로 확인해보겠습니다.
4-2, 3-1 순으로 문제를 풀어야 합니다. 쉬운 문제부터 풀어야 하므로 우선순위 큐에는 3, 4가 들어갑니다.
3번을 풀고 연결된 1번 문제를 풀 수 있으니 우선순위 큐에는 1, 4가 남습니다. 1번을 풀고 4번을 풀고 연결된 2번을 풀 수 있습니다.
이처럼 link [n] == 0인 값들을 쉬운 문제(수가 작은)순으로 풀면 됩니다.
2020/10/02 - [문제풀이/자바] - [백준 2252] 줄 세우기 (자바)
[백준 2252] 줄 세우기 (자바)
https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다..
jellyinghead.tistory.com
여기서 위상정렬에 대한 자세한 설명을 볼 수 있습니다.
메소드
void main
조건을 관리하는 배열인 link와 연결을 관리하는 list를 선언하고 적절히 입력해줍니다.
이 문제를 풀기 위한 자료 구조인 우선순위 큐를 선언하고 link가 0인 값들을 넣어줍니다.
숫자가 작은 것부터 차례대로 꺼낸 후 연결된 값들의 link를 1 감소시키고 0인 것들을 또 우선순위 큐에 넣어주면서 문제를 풀어나갑니다.
'문제풀이 > 백준 && 프로그래머스' 카테고리의 다른 글
| [백준 17081] RPG Extreme (자바) (2) | 2020.10.19 |
|---|---|
| [백준 2146] 다리 만들기 (자바) (0) | 2020.10.16 |
| [백준 1194] 달이 차오른다, 가자. (자바) (0) | 2020.10.14 |
| [백준 12094] 2048 (Hard) (자바) (0) | 2020.10.12 |
| [백준 2957] 이진 탐색 트리 (자바) (0) | 2020.10.11 |