백준 1516 - 게임 개발

 

 

문제 설명

숌 회사에서 이번에 새로운 전략 시뮬레이션 게임 세준 크래프트를 개발하기로 하였다. 핵심적인 부분은 개발이 끝난 상태고, 종족별 균형과 전체 게임 시간 등을 조절하는 부분만 남아 있었다.

게임 플레이에 들어가는 시간은 상황에 따라 다를 수 있기 때문에, 모든 건물을 짓는데 걸리는 최소의 시간을 이용하여 근사하기로 하였다. 물론, 어떤 건물을 짓기 위해서 다른 건물을 먼저 지어야 할 수도 있기 때문에 문제가 단순하지만은 않을 수도 있다. 예를 들면 스타크래프트에서 벙커를 짓기 위해서는 배럭을 먼저 지어야 하기 때문에, 배럭을 먼저 지은 뒤 벙커를 지어야 한다. 여러 개의 건물을 동시에 지을 수 있다.

편의상 자원은 무한히 많이 가지고 있고, 건물을 짓는 명령을 내리기까지는 시간이 걸리지 않는다고 가정하자.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, i번째 건물이 지어지기 위해서 미리 지어져야 하는 건물이 있다.

모든 건물을 짓기 위해 필요한 최소 시간을 구해야 한다.

 

해당 문제는 건물끼리의 순서가 정해져 있다.

하지만, 모든 건물이 연결되어 정렬된 구조는 아니다.

이럴 때 적합한 알고리즘으로 위상 정렬이 있다.

 

위상 정렬을 통해 진입 차수를 관리하면 문제를 쉽게 풀 수 있다.

해당 문제에서 진입 차수는 i번째 건물을 짓기 위해 미리 지어져야 하는 건물이 된다.

어떤 건물이 지어져야 하는지까지 자세하게 관리하지 않고 개수만 관리해도 충분하다.

 

기본적인 논리 흐름은 다음과 같다.

진입 차수가 0인 건물은 해당 건물이 지어지기 전에 지어져야 하는 건물들이 모두 지어졌거나 없었다는 것을 의미한다.

즉, 지금 바로 해당 건물을 지을 수 있다는 말이다.

반대로 진입 차수가 0보다 큰 건물들은 아직 지을 수 없다는 말이 된다.

따라서, 진입 차수가 0인 건물을 미리 구해놓고 해당 건물을 지어야만 지을 수 있는 건물들의 진입 차수를 하나씩 빼준다.

이때, 진입 차수가 0이 되면 그 건물은 바로 지을 수 있기 때문에 큐에 추가한다.

이러한 논리로 전개한다면 문제를 해결할 수 있다.

 

여기서 주의할 점이 있다.

위상 정렬은 원래 여러 가지의 형태를 갖는다.

3
5 -1
2 -1
1 1 2 -1

만약, 위와 같은 입력이 주어진다면 건물을 짓는 순서는 {1, 2, 3}도 가능하지만 {2, 1, 3}도 문제없다.

3번은 1번과 2번이 지어진 이후에 지어지면 되기 때문이다.

하지만, 해당 문제에서 이 순서를 제대로 잡아주지 않으면 문제가 발생할 수 있다.

예를 들어, 1번 건물을 지었을 때 아직 3번 건물의 진입 차수가 0이 되지 않아 건물을 지을 수 없게 된다.

이후, 2번 건물을 지었을 때 비로소 3번 건물의 진입 차수가 0이 되어 지을 수 있기 때문에 2번 건물의 소요 시간인 2를 통해 3번 건물의 소요 시간을 계산할 수 있다.

그렇게 되면 정답인 {5, 2, 6} 이 아니라 {5, 2, 3}이라는 오답을 만들어 낼 것이다.

따라서, 소요 시간이 짧은 건물을 우선적으로 처리하게 된다면 올바른 정답을 찾을 수 있는 위상 정렬 형태를 만들어 낼 것이다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int N;
vector<vector<int>> adj;
vector<int> costs;
vector<int> inDgree;
vector<int> ans;

void Topology()
{
	priority_queue<pair<int,int>> pq;
	for (int i = 1; i <= N; i++)
	{
		if (inDgree[i] == 0)
		{
			pq.push({ -costs[i], i });
			ans[i] = costs[i];
		}
	}

	while (!pq.empty())
	{
		auto [cost, current] = pq.top();
		pq.pop();

		cost *= -1;

		for (auto next : adj[current])
		{
			inDgree[next]--;
			if (inDgree[next] == 0)
			{
				ans[next] = max(ans[next] ,ans[current] + costs[next]);
				pq.push({ -ans[next], next });
			}
		}
	}
}

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

	cin >> N;

	adj.resize(N + 1, vector<int>());
	inDgree.resize(N + 1, 0);
	costs.resize(N + 1, 0);
	ans.resize(N + 1);

	for (int i = 1; i <= N; i++)
	{
		cin >> costs[i];
		
		while (true)
		{
			int prev;
			cin >> prev;

			if (prev == -1) break;
			adj[prev].push_back(i);
			inDgree[i]++;
		}
	}

	Topology();

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

	return 0;
}

---