BOJ 1766 : 문제집

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

1766번: 문제집

이번에도 위상정렬을 쓰는 문제다.

위상정렬을 쓰는 문제들은 그래프에서 순서가 주어지는데, 이 문제에서는 하나의 조건이 더 추가된다.

일단 문제를 풀어 써보자.

 

• 1~N까지 총 N개의 문제들로 구성된 문제집이 있다.
• 1이 가장 쉽고, N이 가장 어렵다.(=번호가 낮을 수록 쉬운 문제이다.)

그리고 주어지는 조건은 다음과 같다.

• N개의 문제를 모두 풀어야 한다.
• 주어진 순서대로 문제를 풀어야 한다. (=위상정렬의 전형적인 조건)
• 가능하면 쉬운 문제부터 풀어야 한다.(=가능하면 번호가 낮은 것 부터 풀어라)

우선, 일반적으로 위상정렬이 어떻게 돌아가는지 정리해보자

1. 진입차수가 0인 정점을 큐에 삽입한다.
2. 큐에서 정점을 꺼내 연결된 모든 간선을 제거(방문 표시)
3. 간선 제거 이후 진입차수가 0이 된 정점을 큐에 삽입
4. 큐가 빌 때까지 2,3 반복 이후 사이클 체크

위의 내용을 읽어보면 진입차수가 0인 정점들이 여러개 있을때, 뭐부터 꺼내야 할지 명확한 조건이 없다.

하지만 문제에서는 낮은 것들부터 뽑으라고 조건을 주고 있다.(쉬운거부터 풀어라)

그러니까, 진입차수가 0인 정점들을 꺼낼 때, 번호가 낮은 것부터 꺼내라는 뜻이다.

이를 위해 구현단계에서 우선순위 큐를 적용시켜주면 된다. -> 낮은 수부터 pop 하도록 설정

 

즉, 위상정렬 문제인데, 사용하는 큐를 우선순위 큐로 바꿔줘서 뽑는 순서를 정해주는 문제이다.

 

소스코드는 깃허브!

https://github.com/onaeonae1/ProblemSovling/blob/master/BOJ%201766.cpp

onaeonae1/ProblemSovling

*위상정렬 문제는 알고 보면 진짜 쉬운데, 가끔 까먹는다. 자주자주 풀어주자.