백준 1516번 게임 개발 (C++)

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

1516번: 게임 개발

 

위상 정렬을 할 수 있으면 50퍼센트는 되는 문제.

 

건물을 미리 지어야하는데 미리 지은 건물들의 시간을 모두 더해야하는 문제이다.

 

위 사진은 기본 예제에서 4를 지을 조건에 2까지 추가한 것이다. 

4를 짓기 위해서는 1,2,3을 지어야한다. 그렇다면, 2,3을 짓고 4를 지어야하는데 2번의 경우 20, 3번의 경우 14이다. 여기서 그냥 위상정렬대로 전입차수가 0이라고 더하면 24가될수도, 18이 될 수 있다.

그러므로 전입차수가 0이 아니라도 영향을 끼칠 수 있음을 알아야한다. 

 

정답코드

#include <iostream>
#include <queue>
#include <map>
#define MAX 501
using namespace std;

vector<int> node[MAX];

int degree[MAX];

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

	int N;
	cin >> N;

	map<int, int> costmap;
	map<int, int> answer;
	queue<int> q;

	for (int i = 1; i <= N; i++) {
		degree[i] = 0;
		int cost, tmp;
		cin >> cost;

		costmap.insert({ i, cost });

		while (cin >> tmp) {
			if (tmp == -1) break;
			node[tmp].push_back(i);
			degree[i]++;
		}
	}

	for (int i = 1; i <= N; i++) {
		if (degree[i] == 0) {
			q.push(i);
			answer[i] = costmap[i];
		}
	}

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

		for (int i = 0; i < node[idx].size(); i++) {
			int next = node[idx][i];
			degree[next]--;				
			answer[next] = max(answer[next], answer[idx] + costmap[next]);

			if (degree[next] == 0) {
				q.push(next);
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		cout << answer[i] << '\n';
	}
}