[백준 1516] 게임 개발 (C++)

문제 링크: https://www.acmicpc.net/problem/1516

1516번: 게임 개발

1. 주의할 점

- 위상정렬 알고리즘의 기초에 대해 알고 있어야 한다

- 사용하는 배열이 많기 때문에 주석 혹은 변수명을 잘 사용한다

- Need_time[] : 해당 번호만을 짓는데 걸리는 시간

- Need_pre[]: 해당 Node를 짓기 위해 남은 선행 Node의 수

- Tot_time[]: 선행 Node들을 모두 지은후 현재 Idx까지 다 지을때 걸리는 시간

 

2. 구현

- 각 Node에 대한 정보를 입력받을 때, 해당 Node를 짓는데 걸리는 시간을 Need_time[] 배열에 저장하고, 각 Node의 선행 Node를 입력받는다면 선행Node의 벡터에 현재 Node를 추가하고, 현재 Node의 Need_pre[] 값을 1 증가시킨다

- 건물을 짓는데 선행으로 지어야하는 Node가 없는 경우, 우선순위큐에 삽입하고 Tot_time[] 배열을 갱신한다

- 우선순위큐가 빌때까지 원소를 1개씩 뽑고, 해당 원소의 벡터에 포함된 하위 Node들의 Need_pre[]값을 1씩 감소한다(선행되어야 하는 Node가 1개씩 줄었다는 의미)

- 하위 Node의 Need_pre[]의 값이 0이 된다면 선행되어야 하는 Node가 모두 지어졌으므로, 우선순위큐에 삽입하고 Tot_time[] 의 값을 갱신한다

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
struct info {
	int idx, val;
};
info tmp;
struct cmp {
	bool operator()(info &a, info &b) {
		return a.val > b.val;
	}
};
vector<int> v[501];		//해당 번호가 선행되어야 하는 번호들
int need_pre[501];		//해당 Node를 짓기 위해 남은 선행 Node의 수
int need_time[501];		//해당 번호만을 짓는데 걸리는 시간
int tot_time[501];		//해당 번호까지 다 짓는데 걸리는 시간

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int node, val;
	cin >> node;
	for (int i = 1; i <= node; i++) {
		cin >> need_time[i];
		while (1) {
			cin >> val;
			if (val == -1) break;
			v[val].push_back(i);
			need_pre[i]++;
		}
	}
	priority_queue<info, vector<info>, cmp> pq;
	for (int i = 1; i <= node; i++) {
		if (need_pre[i] == 0) {
			tmp.idx = i;
			tmp.val = need_time[i];
			pq.push(tmp);
			tot_time[i] = need_time[i];
		}			
	}
	while (!pq.empty()) {
		int cidx = pq.top().idx;
		int cv = pq.top().val;
		pq.pop();
		for (int i = 0; i < v[cidx].size(); i++) {
			int next = v[cidx][i];
			need_pre[next]--;
			if (need_pre[next] == 0) {
				tmp.idx = next;
				tmp.val = cv + need_time[next];
				pq.push(tmp);
				tot_time[next] = tmp.val;
			}
		}
	}
	for (int i = 1; i <= node; i++)
		cout << tot_time[i] << '\n';
	system("pause");
	return 0;
}