#743 (Div.2) C - Book

문제 링크 => Problem - C - Codeforces

Problem - C - Codeforces

---

Topological Sorting 과 dynamic programming 의 짬뽕 문제이다.

 

백준에서만 풀었던 위상정렬을 여기서 풀게되서 뭔가 감회가 새로웠다.

 

문제는 x 번째 책을 읽기 위해서 미리 읽어야 할 책들의 list 가 n개 주어진다.

 

이때, 책을 모두 읽기 위해 걸리는 시간을 구해야 한다.

 

읽어야 할 책 : x, 미리 읽어야 할 책 : y 라고 할 때 x의 진입차수를 높여주고 단방향으로 y => x 를 이어주도록 한다.

 

그렇게 모든 세팅이 끝나면 모든 책들이 읽힐 수 있는지 확인하는 과정을 거친다.

 

즉, 진입차수가 0인 책들을 발견해가면서 모든 책을 읽을 수 있는지 counting 함과 동시에 vector에 읽을 책을 순서대로 push 한다.

 

위 과정이 끝나면 vector 안에 가장 먼저 읽은 책부터 가장 나중에 읽은 책이 순서대로 있는데 reverse를 해준다. (가장 나중에 읽은 책 => 가장 먼저 읽은 책 순서)

 

그리고 counting 값이 n과 동일하지 않다면 모든 책을 읽을 수 없는 경우이므로 -1을 출력한다.

 

여기서부터 dynamic programming 기법이 사용되는데 가장 나중에 읽은 책부터 순서대로 접근해 간다.

 

예를 들어서 책 2를 읽기 위해서 미리 1, 3을 읽어야 한다고 가정하자.

(dp [x] = 책 x를 역으로 읽기 위해 소요되는 시간)

 

먼저 책 2를 읽기 위해서 미리 1, 3을 읽어야 한다고 할 때, 역으로 접근한다면 책 2를 가장 나중에 읽는다고 할 때, dp[2] = 1 로 볼 수 있겠다.

 

즉, 초기에 dp [1~ n] = 1 로 할당해주고 접근해야 하는 것임을 알 수 있겠다.

 

그 다음에 책 1을 읽을 때 dp[1] = 1 인 반면에 책 3을 읽을 때 dp[1] = 2 임을 짐작할 수 있다.

 

순서대로 읽을 때 1 => 2 => 3 => ...  오름차순으로 책을 한 번에 읽을 수 있지만,

                         5 => 4 => 3 => ...  내림차순으로 책을 한 번에 읽을 수 없는 성질을 이용해야 한다.

 

즉 dp[1] 인 경우 1 => 2 인 경우이므로 (1 < 2) dp[2] 값이 되는 반면에

    dp[3] 인 경우 3 => 2 인 경우이므로 (3 > 2) dp[2] + 1 값이 된다.

 

정리하자면 dp[x] = max(dp[x], dp[next] + (x > next ? 1 : 0)) 이 된다.

 

이렇게 해서 dp값 중 최대값이 모든 책들을 읽을 수 있는 경우가 된다.

 

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
#include <string.h>
#include <cstring>
#include <queue>
#include <stack>
#define endl '\n'
#define INF 1000000000
#define ll long long

using namespace std;

int n, inDegree[200001], dp[200001];
vector<int> v[200001];

void initialize() {
	for (int i = 1; i <= n; i++) {
		dp[i] = 1, inDegree[i] = 0;
		v[i].clear();
	}
}

bool isRead(vector<int> &rv) {

	queue<int> Q;
	for (int i = 1; i <= n; i++) {
		if (inDegree[i] == 0) {
			Q.push(i);
		}
	}
	
	int cnt = 0;
	while (!Q.empty()) {
		int x = Q.front();
		rv.push_back(x), cnt++;
		Q.pop();

		for (int next : v[x]) {
			if (--inDegree[next] == 0) {
				Q.push(next);
			}
		}
	}
	
	reverse(rv.begin(), rv.end());

	return cnt == n;
}

void test() {

	int k, x;
	cin >> n;

	initialize();

	for (int i = 1; i <= n; i++) {
		cin >> k;
		for (int j = 0; j < k; j++) {
			cin >> x;
			v[x].push_back(i);
			inDegree[i]++;
		}
	}

	vector<int> rv;

	if (!isRead(rv)) {
		cout << -1 << endl;
		return;
	}

	int result = 0;
	for (int i = 0; i < rv.size(); i++) {
		int x = rv[i], tmp = dp[x];
		for (int next : v[x]) {
			dp[x] = max(dp[x], dp[next] + (x > next ? 1 : 0));
		}
		result = max(result, dp[x]);
	}

	cout << result << endl;
}

int main() 
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int t;
	cin >> t;
	while (t--) test();

	return 0;
}