백준/1516/위상 정렬/게임 개발

백준/1516/위상 정렬/게임 개발

문제 해석

건물을 짓는데 있어 먼저 짓어야 될 건물들이 존재한다.
이 때 각 건물들을 짓는데 소유되는 최대 시간을 구하라.

문제 풀이

1. 우선 해당 건물을 짓는데 필요한 선행 건물들을 저장한다.
2. 해당 건물을 짓는데 필요한 선행 건물들의 시간을 따로 구한다.
3. 마지막으로 해당 건물을 짓는데 필요한 시간을 더한다.

1. 우선 해당 건물을 짓는데 필요한 선행 건물들을 저장한다.

for (int i = 1;i <= N;i++)
{
	int _time = 0;
	int _prev_con_index = 0;
	bool flag = false;
	while (true)
	{
		// 첫 입력은 해당 인덱스 건물을 짓는 시간
		if (!flag)
		{
			cin >> _time;
			built_time[i] = _time;
			flag = true;
		}
		else
		{
			cin >> _prev_con_index;
			if (_prev_con_index == -1)
				break;
			adj_con[_prev_con_index].push_back(i);
			deg[i]++;
		}
	}
}

해당 건물들을 짓는데 필요한 선행 건물들을 짓을때 이 선행 건물을 사용함으로써 짓을 수 있는 건물들을 저장해놓는다.(필요한 건물의 수와 함께)

2. 해당 건물을 짓는데 필요한 선행 건물들의 시간을 따로 구한다.

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

while (!q.empty())
{
	int cur = q.front(); q.pop();
	for (int nxt : adj_con[cur])
	{
		deg[nxt]--;
		result[nxt] = max(result[nxt], result[cur] + built_time[cur]);
		if (deg[nxt] == 0)
			q.push(nxt);
	}
}

선행 건물이 필요없는 건물들을 먼저 추려 짓게하고 이로 인해 지을 수 있는 집들을 선별하는 방법이다.
이 때 max 부분이 중요한데, 즉, 현재 result값에 저장된 값 보다 크게 뽑힌다는 것은 해당 선행 건물 역시 같은 선행 건물이 필요하다는 것을 뜻하고, 그 선행 건물에 현재 건물을 짓는 비용까지 더하면 그 모든 선행 건물을 짓는 시간 비용을 알아낼 수 있다.

3. 마지막으로 해당 건물을 짓는데 필요한 시간을 더한다.

for (int i = 1;i <= N;i++)
{
	cout << result[i]+built_time[i] << '\n';
}

마지막으로 모든 선행건물을 짓는 시간비용에 나 자신을 짓는 시간 비용을 더해주면 해당 건물을 짓는데 필요한 최대의 시간이 나온다.

풀이

첫번째 풀이

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

int built_time[501];
vector<int>adj_con[501];
int deg[501];

queue<int>q;
int result[501];

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

	// 건물 종류의 수
	int N = 0;

	cin >> N;

	for (int i = 1;i <= N;i++)
	{
		int _time = 0;
		int _prev_con_index = 0;
		bool flag = false;
		while (true)
		{
			// 첫 입력은 해당 인덱스 건물을 짓는 시간
			if (!flag)
			{
				cin >> _time;
				built_time[i] = _time;
				flag = true;
			}
			else
			{
				cin >> _prev_con_index;
				if (_prev_con_index == -1)
					break;
				adj_con[_prev_con_index].push_back(i);
				deg[i]++;
			}
		}
	}

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

	while (!q.empty())
	{
		int cur = q.front(); q.pop();
		for (int nxt : adj_con[cur])
		{
			deg[nxt]--;
			result[nxt] = max(result[nxt], result[cur] + built_time[cur]);
			if (deg[nxt] == 0)
				q.push(nxt);
		}
	}

	for (int i = 1;i <= N;i++)
	{
		cout << result[i]+built_time[i] << '\n';
	}

	return 0;
}