[6일차] 그래프1 F - 1516: 게임 개발

골드 Ⅲ

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>//max 함수 쓸라고
using namespace std;

struct Info {
	int indegree = 0;
	int weight;
};

int N, M;
vector<int> nextNode[501];//nextNode[1] = {2, 3, 5} 1 다음에 해야되는 얘들 : 2, 3, 5임
Info Infos[501];//노드들의 weight랑 indegree 저장, 업데이트
queue<int> toStart;
int weightInit[501];//weight 초기정보 저장해놔야 돼서

int main() {
	scanf("%d", &N);
	//정보들 입력받기
	int w;
	for (int i = 1; i <= N; i++) {
		scanf("%d", &w);
		Infos[i].weight = w;
		weightInit[i] = w;
		int num;
		//-1이 나올때 까지 선행건물들 입력받기
		//i건물을 짓기위해서 num을 먼저 지어야 함
		//num -> i
		//num 다음에 오는 얘들이 i임 nextNode[num]에 i 주렁주렁 달아주기
		while(true){
			scanf("%d", &num);
			if (num == -1) break;
			//num을 선행해야 되는 녀석들
			nextNode[num].push_back(i);
			printf("%d노드에 %d 달아줌\n", num, i);
			Infos[i].indegree++;
			printf("%d 노드 indegree++\n", i);

		}
	}

	//위상정렬 하기위해 indgree가 0인 노드번호 tostart에 넣어주기
	for (int i = 1; i <= N; i++) {
		if (Infos[i].indegree == 0) {
			toStart.push(i);
		}
	}
	//위상정렬
	while (!toStart.empty()) {
		//큐에서 indegree 0인거 하나 뽑아줌
		int startNode = toStart.front();
		printf("start node: %d\n", startNode);
		toStart.pop();

		//뽑아준 걸 바탕으로 weight update 해주기
		for (auto i : nextNode[startNode]) {
			//i : startNode가 선행되는 얘들
			//i의 weight에 startNode에 weight 더해주면서
			//i의 선행 노드들이 업데이트 해준 weight값들 중
			//최대값을 취해야함 i가
			//max(현재 i노드의 weight값(업데이트 되었을 수 있음), 원래 i노드의 weight + startNode가 추가하려는 weight 값)
			Infos[i].weight = max(Infos[i].weight, weightInit[i] + Infos[startNode].weight);
			//i의 indegree도 빼주기
			//뺐더니 0이면 toStart에 넣기
			Infos[i].indegree--;
			if (Infos[i].indegree == 0) toStart.push(i);
			printf("업데이트 후\n%d.weight = %d, %d.indegree = %d\n", i, Infos[i].weight, i, Infos[i].indegree);
		}
	}
	//정답 출력
	for (int i = 1; i <= N; i++) {
		printf("%d\n", Infos[i].weight);
	}
}

 

위상정렬 + (각 노드의 weight값이 "모든" 선행노드들에 의하여 영향 받으므로 최대값으로 update 해주기)

 

인 건 알겠는데

왜 위상정렬 여러개 중에 답이 있는게 아니라

그냥 위상정렬로 풀면 답이지?

결국 weight의 최소값을 구하는건데

weight의 최소.. 라는 부분이 어디에 있지?

 

 

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

int N;
int cost[501];
vector<int> nextNode[501];
int indegree[501];
queue<int> toStart;
int dp[501];

int main() {
	scanf("%d", &N);
	int t;
	for (int i = 1; i <= N; i++) {
		scanf("%d", &t);
		cost[i] = t;
		dp[i] = t;

		int num;
		while (true) {
			scanf("%d", &num);
			if (num == -1) break;
			nextNode[num].push_back(i);
			indegree[i]++;
		}
	}
	for (int i = 1; i <= N; i++) {
		if (indegree[i] == 0) toStart.push(i);
	}
	while (!toStart.empty()) {
		int cur = toStart.front();
		//나 나간다~~
		toStart.pop();

		//붙어있던 얘들
		for (int i = 0; i < nextNode[cur].size(); i++) {
			int nN = nextNode[cur][i];
			//이어져있는 노드에 적힌 값보다 크면 업데이트
			//지금까지 newNode에서의 최대값 보다 더 큰 값이 존재할 수 있따면?
			//더 큰 값이란? 원래 newNode cost + 먼저 수행해야하는 노드에서 넘어온 dp값의 코스트!
			if (dp[nN] < cost[nN] + dp[cur]) dp[nN] = cost[nN] + dp[cur];
			if (--indegree[nN] == 0) toStart.push(nN);
		}
	}
	for (int i = 1; i <= N; i++) {
		printf("%d\n", dp[i]);
	}
}

 

새로 푼 거