BOJ1516/ C++

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

1516번: 게임 개발

백준 온라인저지 1516번 문제입니다. 

위상정렬을 이용해서 풀었습니다.

 

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

int n;
int time[501];
int dp[501];
int buildingCnt[501];
vector<int> building[501];

int max(int a, int b) { return a > b ? a : b; }

void Input() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> time[i];
		dp[i] = time[i];
		while (true) {
			cin >> x;
			if (x == -1) break;
			else {
				building[x].push_back(i);
				buildingCnt[i]++;
			}
		}
	}
}

void solution() {
	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (buildingCnt[i] == 0)
			q.push(i);
	}
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (int i = 0; i < building[cur].size(); i++) {
			int next = building[cur][i];
			dp[next] = max(dp[next], dp[cur] + time[next]); //건물을 짓는데 걸리는 시간의 최댓값
			buildingCnt[next]--;
			if (buildingCnt[next] == 0)
				q.push(next);
		}
	}
	for (int i = 1; i <= n; i++)
		cout << dp[i] << "\n";
}
int main(void) {
	Input();
	solution();
}

 

아이디어

위상정렬에서 건물을 짓는데 걸리는 시간의 최댓값을 구하는 부분만 구현