[BOJ1516] 게임개발

[BOJ1516] 게임개발

문제 링크

문제 설명

• 앞선 포스팅 BOJ1005 ACM Craft와 같은 유형의 문제다.

풀이 과정

• 일단 풀이과정은 ACM Craft와 동일하다.

• 하지만 ACM Craft를 풀면서 단순히 DAG에 대한 정점에 가중치가 주어진 Longest Path 문제라는 것을 발견하여, 위상정렬을 한 후 dp를 이용하여 푸는것은 알았지만, 구현을 처음 해봐서 조금 맘에들지 않게 짰었다.

• ACM Craft에선 현재 내가 있는 정점으로 들어오는 indegree에 연결된 정점들을 어떻게 확인하는지에 대해 어려움이 있어서 역방향 그래프를 하나 더 만들어서 풀었었다.

• 이번 문제에서는 bfs를 돌면서 bfs 안에서 dp를 바로 해결하였다.

• 내가 고민했던 문제에 대한 힌트가 bfs안에 있었다. bfs는 내가 현재 있는 점과 다음 점이 있었고, 다음 점의 indegree가 0이 되기 전까지는 큐에 넣지 않으므로, 그 사이에서 dp를 계속 업데이트 시켜두면 해결이 된다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

vector <vector <int>> adj;
queue <int> q;
int weight[505];
int ind[505];
int dp[505];

void bfs() {
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		int size = adj[now].size();
		for (int i = 0; i < size; i++) {
			int next = adj[now][i];
			ind[next]--;
			dp[next] = max(dp[next], dp[now] + weight[next]);
			if (ind[next] == 0)
				q.push(next);
		}
	}
}

int main() {
	int N;
	scanf("%d", &N);
	adj.resize(N + 1);
	for (int i = 1; i <= N; i++) {
		int w;
		scanf("%d", &w);
		weight[i] = w;
		dp[i] = w;
		while (1) {
			int a;
			scanf("%d", &a);
			if (a == -1) break;
			adj[a].push_back(i);
			ind[i]++;
		}
	}
	for (int i = 1; i <= N; i++) {
		if (ind[i] == 0) q.push(i);
	}
	bfs();
	for (int i = 1; i <= N; i++) {
		printf("%d\n", dp[i]);
	}
	return 0;
}

코드리뷰

• ACM Craft 문제를 풀때 다시한번 코드를 짜봐야겠다는 생각을 했었는데 이 문제를 통해서 깔끔하게 푸는 방법을 알게되었고, 조만간 ACM Craft 문제를 다시 풀어봐야겠다.

---