Codeforces Round #743 (Div. 2)-C. Book

문제 설명

$n$개 챕터로 이루어진 책이 있다.
각 챕터는 이해하기 위해서 필요한 다른 챕터의 목록이 있다. 이 목록에 있는 모든 챕터를 읽어야만 이 챕터를 읽고 이해할 수 있다.
현재 당신은 아무 챕터도 이해하지 못한상태이다. 당신은 처음부터 끝까지 책을 반복해서 읽을 것이고, 책에 있는 모든 챕터를 다 이해할때까지 이 과정을 반복한다. 당신이 한 챕터를 읽을때, 그 챕터를 이해하기 위한 목록에 있는 챕터를 모두 읽지 않았다면 당신이 읽은 챕터는 이해한 것이 아니다.
책에 있는 모든 챕터를 이해하기 위해서 반복해서 읽어야하는 책의 최소 횟수를 구해야한다. 혹은 책을 몇번이라도 읽더라도 모든 챕터를 절대로 이해할 수 없는지 결정해야한다.

입력
이 문제는 다수의 테스트케이스가 주어진다. 첫번째 줄에는 테스트케이스의 수 $t$가 주어진다. $(1 \le t \le 2\times10^4)$
각 테스트케이스의 첫번째 줄은 챕터의 수 $n$이 주어진다. $(1 \le n \le 2\times10^5)$
다음 $n$개줄에는 다음과 같이 데이터가 주어진다.
각 $i$번째 줄의 첫번째는 $i$번째 챕터를 이해하기 위해서 필요한 다른 챕터의 수 $k_i$가 주어진다. $(0 \le k_i \le n - 1)$ 그 다음부터는 $i$번째 챕터를 이해하기 위해서 필요한 챕터가 $a_{i,1}, a_{i,2}, ......, a_{i, k_i}$가 $k_i$개 주어진다. $(1 \le a_{i,j} \le n, a_{i,j} \neq i, a_{i,j} \neq a_{i,l} for j \neq l)$

출력
각 테스트케이스마다 만약 책 전체를 이해할 수 있으면 책을 읽은 최소 횟수를, 이해할 수 없으면 -1을 출력한다.

intput
5
4
1 2
0
2 1 4
1 2
5
1 5
1 1
1 2
1 3
1 4
5
0
0
2 1 2
1 2
2 2 1
4
2 2 3
0
0
2 3 2
5
1 2
1 3
1 4
1 5
0

output
2
-1
1
2
5

문제 접근

사용한 알고리즘: 인접리스트, 그래프 이론, 집합, 자료구조
걸린 시간: 00:18
이 문제는 주어진 자료를 어떻게 나타내야 할 지 생각해야하는 좋은 문제였다. 처음 이 문제를 Virtual Contest에서 접했을때는 한 챕터가 이해하기 위해 필요한 다른 챕터들을 인접리스트로 작성하면 좋을 것 같아서 작성을 했는데, 답을 보니까 내가 생각한 것을 조금만 반대로 생각하면 쉽게 풀리는 문제라서 개인적으로 아쉬웠다.

내가 맨 처음에 생각한 방법은 그냥 입력에서 주어진것처럼 1번째 챕터는 2가 필요하고, 2번재 챕터는 필요 없고, .... 이런식으로 인접리스트를 구현했다. 하지만 이렇게 생각하면 어떨까? 1번 챕터를 읽으면 4번 챕터를 이해할 수 있습니다. 2번 챕터를 읽어도 아무것도 이해할 수 없습니다. 이런식으로 말이다. 문제에서 주어진 첫번째 테스트케이스로 이해해보자. 이 방법만 이해하면 문제의 절반은 푼거나 다름없다.

첫번째 케이스는
4
1 2
0
2 1 4
1 2
이렇게 주어졌다. 총 챕터의 수는 4개이고, 첫번째 챕터를 이해하기 위해서는 2번째 챕터가 필요하며 두번째 챕터는 선행 챕터가 필요 없으며 3번재 챕터는 1번째 챕터와 4번째 챕터의 이해가 필수적이다. 마지막 4번째 챕터는 2번째 챕터를 읽으면 이해할 수 있다. 이 케이스를 이렇게 바꾸는 것이다.
1 -> 3
2 -> 1, 4
3 ->
4 -> 3
이 데이터의 의미는 다음과 같다.
1번 챕터를 읽으면 3번 챕터를 이해할 수 있습니다, 2번 챕터를 읽으면 1번, 4번 챕터를 이해할 수 있습니다. 3번 챕터를 읽어도 아무것도 이해할 수 없습니다. 4번 챕터를 읽으면 3번 챕터를 이해할 수 있습니다.

이렇게 데이터를 인접리스트로 구현한다음, 문제 풀이에 본격적으로 들어간다.
케이스를 처음부터 보면서 선행 이해과목이 없는 경우를 set에 다 담는다. 그리고 책은 1챕터부터 순차적으로 읽기 때문에 lower_bound(1)로 문제를 시작한다. 이때 set이 비어있으면 이 책을 아무리 순차적으로 읽어도 아무 챕터도 이해할 수 없기 때문에 -1을 출력하고 테스트케이스를 종료한다.
lower_bound(1)은 위의 케이스에서 2이고, 2에 연결한 값들을 차례로 순회하면 1과 4에 방문한다. 1번 챕터를 이해하기위한 과목은 1개 이기 때문에 2를 읽으면 다 이해하게 된다. 이렇게 다 이해하게 된 과목을 set에 insert한다. 같은 방법으로 4또한 set에 insert한다. 이 것을 다 순회하면 챕터 2는 이해한 것이 되기 때문에 전체값에서 1을 빼고, 총 4과목을 다 이해하면 반복문을 종료하게 되는 방식으로 프로그램을 짰다. 이때 lower_bound에 값이 없으면 맨 마지막 index로 되는데, 이곳에 값이 위치하면 페이지를 처음으로 돌려서 다시 책을 읽게하는 과정으로 반복하게 된다.

소스 코드

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        vector<vector<int>> g(n + 1);
        vector<int> cnt(n + 1);
        set<int> s;
        for(int i = 1; i <= n; i++){
            int num; cin >> num;
            if(!num) s.insert(i);
            cnt[i] = num;
            while(num--){
                int pre; cin >> pre;
                g[pre].push_back(i);
            }
        }
        int total = n;
        int page = 1;
        int ans = 1;
        while(total > 0){
            if(s.size() == 0){
                ans = -1;
                break;
            }
            auto it = s.lower_bound(page);
            if(it == s.end()){
                page = 1;
                ans++;
            }else{
                int p = *it;
                s.erase(it);
                for(int i = 0; i < g[p].size(); i++){
                    int next = g[p][i];
                    cnt[next]--;
                    if(!cnt[next]) s.insert(next);
                }
                total--;
                page = p;
            }
        }
        cout << ans << "\n";
    }
}