[BOJ 1516] 게임 개발

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

1516번: 게임 개발

---

위 문제는 위상 정렬을 이용하여 푸는 문제이다.

 

위상 정렬이란 그래프에서 진입 차수가 0인 노드를 차례대로 제거해나가는 형식의 정렬이다.

 

진입 차수가 0이 되는 순서대로 출력을 하는것이다. 

 

위 문제에 대입해보자면, 어떤 건물을 짓기 위해 지어야하는 건물들의 관계를 그래프로 그려보면, 어떤 건물을 짓기 위해 먼저 지어야하는 건물의 수가 진입차수가 되게 된다.

 

위 문제의 예제를 그래프로 그려보면 아래와 같이 된다.

위 그래프에서 진입 차수가 0인걸 차례대로 제거해나가면서 건물이 지어지는 시간을 갱신하면 된다.

 

4번 건물의 경우 1번, 3번 건물이 지어져야 지어지는데, 3번 건물은 1번 건물이 지어져야 건설이 가능하니

1 -> 3 -> 4번 순으로 건물을 건설하면 총 18이라는 시간이 소모된다. 

---

#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

int n;
vector<vector<int>> g;
pair<int, int> gInfo[501];
int ans[501];

int main()
{
	scanf("%d", &n);
	g.resize(n + 1);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &gInfo[i].first);
		while (1)
		{
			int t;
			scanf("%d", &t);
			if (t == -1)
				break;

			g[t].push_back(i);
			gInfo[i].second++;
		}
	}

	queue<int> q;

	for (int i = 1; i <= n; i++)
	{
		if (gInfo[i].second == 0)
		{
			q.push(i);
		}
		ans[i] = gInfo[i].first;
	}

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

		for (auto s = g[p].begin(); s != g[p].end(); s++)
		{
			if (--gInfo[*s].second == 0)
				q.push(*s);
			ans[*s] = max(ans[*s], gInfo[*s].first + ans[p]);
		}
	}

	for (int i = 1; i <= n; i++)
	{
		printf("%d\n", ans[i]);
	}
}