백준 1516 - 게임 개발(C++)

문제 링크입니다! https://www.acmicpc.net/problem/1516

1516번: 게임 개발

문제 조건

출력 예시

그래프를 사용한 DP 문제였습니다.

먼저 지을 수 있는 건물을 지은 다음, 해당 건물을 짓고 난 다음에 지을 수 있는 건물을 지어보는 식으로 최댓값을 찾아가는 문제였습니다.

ex) 1 -> X , 2 -> X , 3 -> 2 , 4 -> 1,2 , 5 -> 1,3  (A -> B는 B를 짓고 나서 A를 지을 수 있다는 의미입니다.)

     해당 경우, 1번과 2번을 먼저 짓습니다. 

     1번과 2번을 짓고 난 뒤에 지을 수 있는 건물은 3번, 4번 ,5번입니다. 따라서 해당 건물를 짓는데 걸리는 시간을 계       산합니다. 

     3번을 짓고 난 뒤에 지을 수 있는 건물을 5번입니다. 따라서 5번을 다시 확인해줍니다.

 

문제 접근 방법

1. i번 건물을 지을 때 필요한 건물의 갯수와 몇번을 지어야지 i번 건물을 지을 수 있는지를 저장합니다.

2. 먼저 지을 수 있는 건물들을 먼저 지어줍니다.(선행 건물이 필요없는 건물일 경우)

3. X번을 지은 뒤 지을 수 있는 건물들을 확인해주고, 필요한 건물의 갯수를 하나 빼줍니다.

4. 탐색 중, 필요한 건물의 갯수가 0이 된 건물의 경우 queue에 넣어줍니다.

 

 

자세한 것은 코드를 참고해주세요!

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

int N;
vector<int> build[501];
int dp[501];
int build_time[501];
int connect[501];
typedef struct qu {
	int x;
	int t;
}qu;
queue<qu> q;

void bfs() {
	while (!q.empty()) {
		int x = q.front().x;
		int t = q.front().t;
		q.pop();
		for (int i = 0; i < build[x].size(); i++) {
			int xx = build[x][i];
			dp[xx] = max(dp[xx], dp[x] + build_time[xx]);
			connect[xx]--;
			if (connect[xx] == 0) {
				q.push({ xx,dp[xx] });
			}
		}
	}
}

void solve() {
	bfs();
	for (int i = 1; i <= N; i++) {
		cout << dp[i] << "\n";
	}
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		int t;
		cin >> t;
		build_time[i] = t;
		while (1) {
			int num;
			cin >> num;
			if (num == -1) break;
			connect[i]++;
			build[num].push_back(i);
		}
	}
	for (int i = 1; i <= N; i++) {
		if (connect[i] == 0) {
			dp[i] = build_time[i];
			q.push({ i, dp[i] });
		}
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!