[백준][C++]1516번. 게임 개발

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

 

이 문제는 먼저 지어야하는 건물이 있는 경우가 존재하고 이를 통해 건물 간의 건설 순서를 정해 주어야하는데 이때

위상정렬을 통해 풀 수 있다. 계산 과정에서 중요한 점은 아래와 같은 코드인데

answer[i] = max(answer[i], answer[cur] + apart_time[cur])

cout << answer[i] + apart_time[i] << "\n";

 

answer[i]는 건물 i를 짓기까지 걸린 총 시간으로 answer[cur] + apart_time[cur]는 현재 건물 cur까지 짓는 데 걸린 시간에 현재 건물의 건축 시간을 더한 것으로 이전까지 계산된 answer[i] 값과 현재 건물 cur을 통한 경로로부터의 시간 중 더 큰 값을 선택하기 위한 코드이고 

 

마지막에 출력하는 부분은 건물 i를 짓기 위해 필요한 모든 선행 건물들이 지어지는 데 걸린 누적 시간이고 실제로 건물 i를 짓는 시간이므로, 최종적으로 두 값을 더해줘야 건물 i가 완성되는 데 걸린 총 시간을 계산할 수 있다.

 

 

정답코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<vector<int>> apartments;
vector<int> apart_time;
vector<int> indegree;		//진입 차수배열
int main()
{
	int n;
	cin >> n;

	apartments.resize(n + 1);
	apart_time.resize(n + 1);
	indegree.resize(n + 1);

	//각 건물정보 입력
	for (int i = 1; i <= n; i++)
	{
		//각 시간 입력
		cin >> apart_time[i];

		//먼저 지어야하는 건물 입력
		while (true)
		{
			int apt;
			cin >> apt;

			if (apt == -1) break;
			
			apartments[apt].push_back(i);
			indegree[i]++;
		}
	}

	queue<int> q;

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

	vector<int> answer;
	answer.resize(n + 1);

	while (!q.empty())
	{
		int cur = q.front();
		q.pop();
		for (int i : apartments[cur])
		{
			indegree[i]--;
			//기존 값 vs 선행 건물 시간추가 
			answer[i] = max(answer[i], answer[cur] + apart_time[cur]);
			if (indegree[i] == 0)
			{
				q.push(i);
			}
		}
	}

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