BOJ 2056 - 작업 (위상정렬)

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

오랜만에 그래프문제

 

<문제설명>

최대 10000개 작업들의 순서와 각 작업을 수행하는 데 걸리는 시간이 주어질 때 모든 작업이 끝나는데 걸리는 시간을 구해라.

 

 

<풀이>

예제의 상황을 그래프로 그리면 다음과 같다.

5번 작업을 수행하기 위해선 2번과 4번 작업이 모두 끝나야 한다.

 

1. i번까지 작업을 완료하는데 걸리는 시간을 d[i]라고 하고, 처음에 0으로 초기화 한다.

 

2. ind[i] == 0 인 정점들만 작업하는데 걸리는 시간으로 d를 초기화 한다.

 

3. 위상정렬된 순서대로 정점들을 방문하면서 d[next] = max(d[next], d[curr]+work[next])로 초기화해준다.

 

4. 위상정렬 후 d[i]중 최대값을 출력한다.

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int MAX = 1e4 + 5;

int main() {
	int ind[MAX] = { 0 }, n, a[MAX], d[MAX] = { 0 };
	queue<int> q;
	vector<int> adj[MAX];

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

	for (int i = 1; i <= n; i++)
		if (ind[i] == 0) {
			q.push(i);
			d[i] = a[i];
		}

	
	while (!q.empty()) {
		int curr = q.front(); q.pop();

		for (int next : adj[curr]) {
			d[next] = max(d[next], d[curr] + a[next]);
			if (--ind[next] == 0) q.push(next);
		}
	}

	int ans = 0;
	for (int i = 1; i <= n; i++) ans =max(ans, d[i]);

	cout << ans << '\n';

}

 

 

<생각>

다익스트라에서의 로직과 유사하다. 주의깊게 봐야될듯

 

최장경로문제? 라고 할 수 있을 것 같다.

 

f(i) : i가 끝나는데 걸리는 시간으로 둔다면, 위 예제는 f(7) = max(f(3), f(5), f(6))이다. 재귀로 풀 수도 있을 것 같다.