문제

• 
• 시간 제한: 2초
• 메모리 제한: 128MB

Problem Analysis

문제 간의 정해진 순서를 거스르지 않고 정렬해야 한다는 점에서 Topological Sorting 문제이다. 그런데, 문제를 풀 때마다 다음번에 풀 수 있는 문제의 pool이 달라지고, 그때마다 가장 쉬운 문제를 풀어야 한다. 그렇기에 stack의 top과 인접한 nodes에 우선적으로 접근하는 DFS는 어울리지 않고, 다른 방법으로 풀어야 한다.

Algorithm

kahn's algorithm을 조금 변형해서, priority_queue를 사용한다. 이를 통해, 전체 가능한 선택지 중에서도 가장 쉬운 문제를 우선적으로 접근할 수 있다.

Data Structure

- priority_queue<int> bfs_q : bfs용 queue
- queue<int> topological_order: topological order를 저장하기 위함

결과

Other

시간 복잡도는 topological sort 자체는 O(N)이고, 매 loop마다 priority_queue에 새로운 문제를 추가하는데 O(logN)이므로, 전체 시간 복잡도는 O(NlogN) 이다.