BOJ 백준 1516 게임 개발 <위상 정렬>

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

< 게임 개발 >

 이번 문제는 문제를 제대로 이해하지 못해 고생했다.

특정 건물을 짓기 위해 다른 건물을 먼저 지어야 한다는 간단한 위상 정렬 문제이다.

그런데 나는 건물이 동시에 건설된다는 생각을 하지 못하고, 어리석게도 한 건물씩 지어야 한다고 생각했다.

예를 들어

1. A를 짓기 위해 B를 지어야 한다.

2. A를 짓기 위해 C를 지어야 한다.

3. B를 짓기 위해 D를 지어야 한다.

라는 세 가지 조건이 있다고 했을때, A를 지을 때 고려해야 하는 시간은, 동시에 지을 수 있으므로 

B + C 가 아닌, B와 C 중 더 많이 걸리는 시간만 고려해주면 된다.

#include <iostream>
#include <vector>
#include <queue>
#define SIZE 501

using namespace std;
int n;

int time[SIZE];
int totalTime[SIZE];

int idg[SIZE];
bool visit[SIZE];
vector<int> vtx[SIZE];

void solution()
{
	queue<int> q;

	for (int i = 1; i <= n; ++i)
	{
		if (!idg[i])
			q.push(i);
	}

	while (!q.empty())
	{
		int qsize = q.size();

		for (int i = 0; i < qsize; ++i)
		{
			int cur = q.front();
			q.pop();
			idg[cur] = -1;
			
			for (int next : vtx[cur])
			{
				idg[next]--;
				if (idg[next] == 0)
					q.push(next);

				int tempTime = totalTime[cur] + time[cur];
				if (totalTime[next] < tempTime)
					totalTime[next] = tempTime;
			}
		}
	}
	for (int i = 1; i <= n; i++)
	{
		cout << totalTime[i] + time[i] << '\n';
	}

}

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

	cin >> n;

	vtx->resize(n + 1);
	for (int i = 1; i <= n; ++i)
	{
		cin >> time[i];

		while (true)
		{
			int temp;
			cin >> temp;
			if (temp == -1) break;
			vtx[temp].push_back(i);
			++idg[i];
		}
	}
	solution();

	return 0;
}