[G3] 백준 1516번 게임 개발 C++ 위상 정렬

리뷰

 

게임 상에서 각 건물이 지어질 수 있는 최소 시간을 구하는 문제 위상 정렬을 통해 쉽게 해결할 수 있다.

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

 

문제 풀이

1. 건물의 개수 n과 각 건물의 건설 시간 t배열, 인접 리스트용 벡터 path를 전역 변수로 초기화 해준다.
2. input 함수를 통해 n값을 입력 받고 1~n번째 건물의 건설 시간과 인접 리스트를 입력 받아준다.
3. solution함수를 통해 각 건물의 건설 완료 시간을 구해줄 수 있다.
4. 각 건물의 건설 완료 시간 벡터 sum과 건물을 짓기위한 우선순위의 개수 벡터 cnt를 n + 1, 0값으로 초기화 한다.
5. 각 건물의 인접리스트를 순회하며 인접 리스트에 저장된 건물의 cnt를 1개씩 늘려준다.
6. 정수형 큐 q를 주비하고 cnt가 0인 건물 즉, 바로 지을 수 있는 건물을 큐에 삽입, sum[i]를 t[i]로 갱신한다.
7. 큐가 빌때까지 while루프를 돌며 각 건물의 인접리스트의 sum값을 갱신해 준다.
8. 매번 탐색 될때마다 해당 건물의 cnt를 줄여주며 0이 될 경우 해당 건물의 번호를 큐에 삽입해 준다.
9. 탐색이 완료되면 1 ~ n번의 건물의 sum값을 출력하고 줄바꿈을 해주면 된다.

 

참고 사항

위상 정렬의 스켈레톤 코드를 짤 줄 안다면 로직이 금방 잡힐 것이다.

 

 

정답 코드

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

using namespace std;

int n;
int t[501];

vector<int> path[501];

void input() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> t[i];
		while (1) {
			int node; cin >> node;
			if (node == -1) break;
			path[node].push_back(i);
		}
	}
}

void solution() {
	vector<int> sum(n + 1, 0);
	vector<int> cnt(n + 1, 0);
	for (int i = 1; i <= n; i++) {
		for (int nn : path[i]) cnt[nn]++;
	}

	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (!cnt[i]) {
			q.push(i);
			sum[i] = t[i];
		}
	}

	while (!q.empty()) {
		int cn = q.front(); q.pop();
		for (int nn : path[cn]) {
			sum[nn] = max(sum[nn], sum[cn] + t[nn]);
			if (--cnt[nn] == 0) q.push(nn);
		}
	}

	for (int i = 1; i <= n; i++) cout << sum[i] << "\n";
}

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

	input();
	solution();
}