[BOJ/백준 1516/C++] 게임 개발

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

1516번: 게임 개발

 

[문제 설명]

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

- 게임 플레이에 들어가는 시간은 상황에 따라 다를 수 있기 때문에, 모든 건물을 짓는데 걸리는 최소의 시간을 이용하여 근사하기로 하였다. 어떤 건물을 짓기 위해서 다른 건물을 먼저 지어야 할 수도 있기 때문에 문제가 단순하지만은 않을 수도 있다.

- 예를 들면 스타크래프트에서 벙커를 짓기 위해서는 배럭을 먼저 지어야 하기 때문에, 배럭을 먼저 지은 뒤 벙커를 지어야 한다. 여러 개의 건물을 동시에 지을 수 있다.

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

 

[문제 조건]

- 첫째 줄에 건물의 종류 수 N (1 ≤ N ≤ 500)이 주어진다.

- 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다.

- 건물의 번호는 1부터 N까지로 하고, 각 줄은 -1 로 끝난다.

- 각 건물을 짓는데 걸리는 시간은 100,000보다 작거나 같은 자연수이다. 

 

[문제 설명]

문제에서 요구하는 정답은 각 건물이 완성되기까지 걸리는 최소 시간을 구하는 것이다.

 

일단 문제를 이해해보기 위해 주어진 예제를 살펴보자.

5
10 -1
10 1 -1
4 1 -1
4 3 1 -1
3 3 -1

예제는 이렇게 주어져있다. 이것을 해석해보자면, 예를들어 3번건물은 짓는데 4의 시간이 필요하고, 짓기 전에 1번건물을 먼저 지어야 한다. 이것을 그래프로 한번 표현해보자

 

위 그림은 화살표가 의미 하는 것은 예를들어 1→3의 경우 3번을 짓기 위해서 1번을 먼저 지어야 한다는 뜻이다.

 

다른 번호를 예를 들어보면 4번의 경우 1번과3번이 건설되야지만 지어질 수 있다는 뜻이다.

 

먼저 각 건물이 완성되기까지 걸리는 시간을 구하는 방법을 생각해보자. 주어진 예제를 이용해 확인해보면

 

1번 건물은 건설하는데 10초가 걸리고, 먼저 지어야 하는 건물은 없다. ( 10초 )

2번 건물은 건설하는데 10초가 걸리고, 1번 건물이 먼저지어져야 하기 때문에 10초가 추가로 더 걸린다. ( 20초 )

3번 건물은 건설하는데 4초가 걸리고, 1번 건물이 먼저지어져야 하기 때문에 10초가 추가로 더 걸린다,. ( 14초 )

그 다음 4번 건물은 몇초가 걸릴까? 4번 건물은 1번과 3번 건물이 완성되야 건설이 가능하다. 따라서 1번이 건설되었다고 해도 3번이 아직 건설이 되어있지 않으면 4번은 지을 수 가 없다. 따라서 4번을 짓는데 걸리는 시간은 3번건물이 완성되는데 걸리는시간 14초 + 4번 건물 건설 시간 4초해서 총 18초가 걸린다.

 

따라서 N번 건물을 짓는데 걸리는 시간은 N번을 짓기 위해 먼저 지어야하는 건물들의 소요시간 중 가장 오래걸리는 시간 + N번 건물 건설 시간이 N번 건물을 짓는데 걸리는 시간이 된다.

 

위와 같이 일의 순서를 정해야 할때 쓰는 방법으로 위상정렬이 있다.

 

위상 정렬은 방향성 그래프에서만 사용이 가능하고, 사이클이 존해할 경우 사용이 불가능 하다.

 

위상정렬을 구현하는 방법은 다음과 같다.

• 진입차수가 0인 정점을 큐에 삽입한다.
• 큐에서 정점을 꺼내 연결된 모든 간선들을 제거 ( 연결된 정점의 진입차수를 1 감소시킨다 )
• 진입차수를 1씩 감소시켰을 때 진입차수가 0이된 정점들을 큐에 삽입
• 큐가 완전히 빌때까지 2번과 3번 과정을 반복

큐에서 원소를 꺼낼때 각 건물의 건설시간을 갱신해주면 최종적으로 각 건물을 짓는데 걸리는 시간을 구할 수 있다.

 

위의 과정을 그림으로 나타내보면

 

초기상태

여기서 진입차수가 0인 1번 건물을 제거하고 연결된 2번,3번,4번에 걸리는 시간을 추가해준다. 

큐에는 2번, 3번 ,4번이 들어가 있을 것이다.

그 다음 진입차수가 0인 2번 노드를 확인하면 따로 연결된 정점이 없으니 2번건물 자신이 지어지는데 걸리는 시간을 추가한다.

다음 3번노드를 확인하면 현재까지 걸리는 시간에다가 자신을 짓는 걸리는 시간을 추가하고, 연결된 4번과 5번에 값을 갱신해주는데 기존에 있던 값과 비교했을때 오래 걸리는 시간으로 갱신해준다.

3번 건설시간 = 14초, 1번 건설했을때 갱신했던 값 = 10초

둘 중 더 오래 걸리는 시간인 14초로 갱신

다음 4번으로 4번과 5번 모두 자신의 건설 시간을 추가

(최종상태)

 

[소스 코드]

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <deque>
#include <math.h>
#include <map>
#include <queue>
#include <stack>

using namespace std;

int n;
vector<int> cost;
vector<int> ans;
vector<vector<int>> list;
vector<int> in_out;
vector<bool> ck;

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

	cin >> n;
	cost.resize(n + 1);
	ck.resize(n + 1);
	list.resize(n + 1);
	in_out.resize(n + 1);
	ans.resize(n + 1);

	for (int i = 1; i <= n; i++)
	{
		cin >> cost[i];
		int tmp;
		while (1)
		{
			cin >> tmp;
			if (tmp == -1) break;
			else
			{
				list[tmp].push_back(i);
				in_out[i]++;
			}
		}
	}

	queue<int> q;
	for (int i = 1; i <= n; i++)
	{
		if (in_out[i] == 0)
		{
			q.push(i); ck[i] = true;
		}
	}
	
	while (!q.empty())
	{
		int tmp = q.front(); q.pop();

		ans[tmp] += cost[tmp];

		for (int i = 0; i < list[tmp].size(); i++)
		{
			ans[list[tmp][i]] = max(ans[list[tmp][i]], ans[tmp]);
			in_out[list[tmp][i]]--;
		}
		for (int i = 1; i <= n; i++)
		{
			if (in_out[i] == 0 && !ck[i])
			{
				q.push(i); ck[i] = true;
			}
		}	
	}
	for (int i = 1; i <= n; i++) cout << ans[i] << "\n";
}

굳