BOJ - 1516번 게임 개발 (C++)

문제 출처: https://www.acmicpc.net/problem/1516

문제 난이도

Gold 3

문제 접근법

일단, 먼저 건물을 지어야하는 것이 있다는 면에 있어 위상 정렬이 바로 떠올랐다.
여기서 주의할 점은
1) 만약 4가 지어야하는 건물이 2번과 3번 건물이 있는데 3번이 아무리 빨리 끝내도 2번이 3번보다 걸리는 시간이 크다면 4번은 2번까지 끝내고 나서야 본인 건물을 지을 수 있다.
그래서 문제 그대로 최소 시간을 구하는게 아니라
time[next] = max(time[next], time[now]+duration[next] 가 된다.
2) time 배열 값을 duration 값으로 초기화 해준다. 그래야 위의 식에서 비교가 가능하고 1번 duration까지 따로 더하지 않아도 된다!

통과 코드

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

using namespace std;

int degree[501];
vector<int> arr[501];
int time[501];
int duration[501];

int main() {
	int N;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		int t;
		cin >> t;
		duration[i] = t;
		while (true) {
			int n;
			cin >> n;
			if (n == -1) break;
			degree[i]++;
			arr[n].push_back(i);
		}
	}
	queue<int> q;
	for (int i = 1; i <= N; i++) {
		if (degree[i] == 0) {
			q.push(i);
			time[i] = duration[i];
		}
	}
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		for (int i = 0; i <arr[now].size(); i++) {
			int next = arr[now][i];
			time[next] = max(time[next], time[now] + duration[next]);
			degree[next]--;
			if (degree[next] == 0) {
				q.push(next);
			}
		}
	}
	for (int i = 1; i <= N; i++) cout << time[i]<< "\n";

	return 0;
}

피드백

위상 정렬을 바로 떠올려서 구현한 건 좋았는데 , 그 다음 건물을 짓는 시간에서 헷갈려서 완전 오답이 나왔다..
그래서 다른 분꺼보고 이해하고 풀 수 있었다. 그림하고 같이 있으니, 왜 max로 쳐줘야하는지 이해가 안가면 이 링크를 타고 가서 이해해도 좋다.