백준 1516 c++ "게임 개발" -PlusUltraCode-

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

 

 

[필자 사고]

 

순서가 정해져 있는 문제이다.

즉 위상정렬 알고리즘을 이용하면 쉽게 풀 수있다.

 

이 문제만의 key point 는 순서가 정해진 건물에서 시간값을 어떻게 갱신하냐의 문제이다.

 

이 문제만의 key point는 순서가 정해진 건물들에서 어떻게 효율적으로 시간값을 갱신하느냐에 달려있다.

필자는 이를 해결하기 위해 위상 정렬을 이용한 작업 시간 계산을 도입했다.

먼저, 선행 작업이 없는 건물들, 즉 바로 시작할 수 있는 건물들을 큐에 넣고 위상 정렬을 진행한다.

그런 다음, 큐에서 건물을 하나씩 꺼내며, 해당 건물이 선행 작업으로 필요한 다른 건물들의 완료 시간을 효과적으로 갱신해 나간다.

 

만약, 어떤 건물의 선행 작업 수가 0이 되면, 그 건물을 큐에 추가하여 다음 작업을 이어간다.

 

이렇게 순차적으로 작업을 처리함으로써 각 건물의 최소 완료 시간을 정확하게 계산할 수 있다."

 

필자는 

resultTime[nextNum] = max(resultTime[nextNum] , resultTime[nowNum]+Time[nextNum]);  방식으로 갱신해주었다.

 

 

[소스 코드]

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

using namespace std;

vector<vector<int>> arr;
vector<int> D;
vector<int>Time;
vector<int> resultTime;
int N;

void Input() {
	cin >> N;
	arr.resize(N + 1);
	D.resize(N + 1);
	Time.resize(N + 1);
	resultTime.resize(N + 1);
	

	for (int i = 1; i <= N; i++) {
		int time;
		cin >> time;
		Time[i] = time;
		while (1) {
			int start;
			cin >> start;
			if (start == -1)break;
			D[i]++;
			arr[start].push_back(i);
		}
	}
	resultTime = Time;
}



void BFS(queue<int> &myQueue) {

	while (!myQueue.empty()) {
		int nowNum = myQueue.front();
		myQueue.pop();

		for (int nextNum : arr[nowNum]) {
			D[nextNum]--;
			resultTime[nextNum] = max(resultTime[nextNum], resultTime[nowNum] + Time[nextNum]);
			if (D[nextNum] == 0) {
				myQueue.push(nextNum);
				
			}
		}
	}

}


void GameStart() {
	queue<int> myQueue;

	for (int i = 1; i <= N; i++) {
		if (D[i] == 0) {
			myQueue.push(i);
			}
	}
	BFS(myQueue);

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

int main(void) {

	Input();
	GameStart();
}