백준 / 1516 게임 개발 C++

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

1516번: 게임 개발

처음에 dp문제인 줄 알고 풀려했다가 잘 안 되어 검색해보니 위상정렬을 이용한 문제였습니다.

위상 정렬의 개념을 이해하고 나니 어려운 문제는 아니었습니다.

 

위상 정렬은 순서가 정해져 있는 작업을 처리할 때, 순서를 결정하는 알고리즘입니다.

단, 조건은 사이클이 존재하지 않는 그래프입니다. (DAG)

 

알고리즘은 다음과 같습니다.

1. 각 노드의 차수를 구한다. (진입하는 차수, 아래 그림에서 1의 차수는 0, 5의 차수는 2)

2. 차수가 0인 노드를 큐에 삽입한다.

3. 큐에서 노드를 꺼내어 해당 노드가 연결된 간선을 제거한다.

4. 이후 차수가 0이된 노드를 큐에 삽입한다.

5. 3,4번을 반복하고, 큐가 비어 있게 되면 종료한다.

 

노드가 다음 처럼 주어져있다고 합시다.

 

 

노드	1	2	3	4	5
차수	0	1	1	1	2

 

차수가 0인 노드인 1을 큐에 삽입합니다.

=> queue = { 1 }

 

queue의 front인 1을 꺼내 1과 연결된 간선을 제거 합니다.

노드	1	2	3	4	5
차수	0	0	0	1	2

sort = { 1 }

 

차수가 0이 된 2,3을 큐에 넣습니다.

=> queue = { 2, 3 }

 

마찬가지로 queue에서 2, 3을 순서대로 꺼내고, 2, 3에 연결된 간선을 제거합니다.

sort = { 1, 2, 3 }

차수가 0이된 4를 큐에 넣습니다.

=> queue = { 4 }

 

큐에서 4를 꺼내고, 4에 연결된 간선을 제거합니다.

sort = { 1, 2, 3, 4 }

차수가 0이 된 5를 큐에 넣습니다.

=> queue = { 5 }

 

큐에서 5를 꺼내고, 5에 연결된 간선을 제거합니다. (사실 없습니다.)

 

sort = { 1, 2, 3, 4, 5 }

queue가 비어있게 되므로 종료합니다.

 

정렬이 1, 2, 3, 4, 5순으로 되었습니다.

 

 

이를 문제에 적용해봅시다.

문제에서는 건물을 동시에 여러개 지을 수 있고, 건물을 짓기 위해 먼저 지어야하는 건물이 존재합니다. 이 먼저 짓는 건물과 이로 인해 지을 수 있는 건물을 위의 노드들에 대입할 수 있습니다.

 

그리고 건물마다의 차수를 구하고, 해당 노드 별로 간선이 어디에 연결되어있는 지를 구합니다.

(ex. building[3] = { 4, 5 } => 3->4, 3->5 로 연결된다)

 

그리고 위상정렬을 진행하여, 간선이 0인 노드들에 대해 다음 노드의 result와 간선이 0인 노드의 result + 이를 짓는 데 걸리는 시간을 비교합니다. 

( result[next] = max( result[next], result[node] + basic[node] )

(result : 먼저 지어야할 건물을 고려한 결과, basic : 해당 건물만 짓는데 걸리는 시간)

 

이를 queue가 비게 될 때까지 진행합니다. 

최종 결과는 result + basic 값을 나타내면 됩니다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;

int n;
int degree[501];
int basic[501];
int result[501];
vector<int>building[501];

void make_building()
{
	cin >> n;
	memset(degree, 0, sizeof(degree));
	memset(basic, 0, sizeof(basic));
	memset(result, 0, sizeof(result));

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

		while (1)
		{
			int node;
			cin >> node;
			if (node == -1)
				break;

			degree[i]++;
			building[node].push_back(i);
		}
	}
}

int main()
{
	make_building();
	queue<int>q;
	for (int i = 1; i <= n; i++) {
		if (degree[i] == 0)
			q.push(i);
	}

	while (!q.empty()) {
		int node = q.front();
		q.pop();

		for (int i = 0; i < building[node].size(); i++) {
			int next = building[node][i];
			result[next] = max(result[next], result[node] + basic[node]);

			degree[next]--;
			if (degree[next] == 0)
				q.push(next);
		}
	}

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