BOJ 1766 - 문제집

[이전 블로그]에서 글 옮김

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

풀이

처음에는 문제의 접근 방향을 후위순회처럼 생각했다. 어떤 x번째를 하기 위해서 그 이전것을 무조건 해결해야하는 방식.
틀리고 나서 문제를 다시 이해했는데, 깨달은 테스트 케이스부터 말하자면 아래와 같다.

5 3

4 1

2 3

5 3

내가 생각한 이 입력의 정답은 아래와 같다.

2 4 1 5 3

1번보다 4번을 먼저 풀어야하고, 3번보다 2, 5번을 먼저 풀어야한다. 1번을 풀기 위해서 4번을 풀어야하는데, 같은 우선순위에서 4번보다는 2번이 쉽다.
(둘 다 1개의 문제 앞에 있음)2번을 풀고 4번을 풀면, 1번이 풀리고 남은 5번을 풀면 3번이 풀린다.

처음에 생각한 대로라면 4 1 2 5 3 이 나와야하는데, 이게 틀려서 위 생각으로 다시 풀었더니 맞았다.

위상정렬 도중에 indegree가 없는 정점을 선택할때마다 번호가 작은(문제 난이도가 낮은) 정점을 선택하게 하면 된다.

코드