[백준 BOJ 1516 gold3 - 게임 개발] 위상정렬(topological sort) C++

 

백준 1516 게임 개발

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

1516번: 게임 개발

 

어떤 건물을 짓기 전에 먼저 지어야 하는 건물이 있다는 조건에서 위상정렬을 떠올릴 수 있다. 

#include<iostream>
#include<string>
#include<algorithm>
#include<string.h>
#include<string>
#include<vector>
#include<queue>

using namespace std;

int N;
int period[501];
vector <int> adj[501];
int indegree[501];
int dab[501];
queue <int> q;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N;
	int t;
	for (int i = 1; i <= N; i++) {
		cin >> t;
		period[i] = t;

		int x = 0;
		while (x != -1) {
			cin >> x;
			if (x == -1)break;
			adj[x].push_back(i);
			indegree[i]++;
		}
	}

	for (int i = 1; i <= N; i++) {
		if (indegree[i] == 0) {
			q.push(i);
			dab[i] = period[i];
		}
	}

	while (!q.empty()) {
		int top = q.front();
		q.pop();
		//dab[top] += peri[top];

		for (int i = 0; i < adj[top].size(); i++) {
			int next = adj[top][i];
			indegree[next]--;

			dab[next] = max(dab[next], dab[top] + period[next]);

			if (indegree[next] == 0) {
				q.push(next);
				//dab[next] += dab[top];
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		cout << dab[i] << "\n";
	}
}

주석 처리 해놓은 코드로 처음에 냈다가 틀렸습니다가 떴다. 

 

중요한 것은

dab[next] = max(dab[next], dab[top] + period[next]);

부분이다.