위상 정렬 - 게임 개발하기

<문제>

백준 - 1516: 게임 개발하기

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

1516번: 게임 개발

<문제 접근>

2차원 벡터를 생성해 각 건물마다 먼저 지어야할 건물에 대한 정보를 입력한 후 BFS를 이용해 각 건물의 건축 시간을 계산하는 방식으로 접근했다.

 

<슈도 코드>

→ 문제를 풀면서 기존 슈도코드와 많이 달라져 실패한 코드 올림

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector <vector<int>> v;
vector <vector<int>> v_build;
vector <int> cost;
vector <int> re_cost;
vector <int> visited;
queue <int> q;
int n;

void cal_cost(int b);

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int value;
	cin >> n;

	cost.resize(n + 1);
	re_cost.resize(n + 1, 0);
	v.resize(n + 1);
	visited.resize(n + 1, 0);
	v_build.resize(n + 1);

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> value;
			if (value == -1) {
				break;
			}
			else {
				v[i].push_back(value);
			}
		}
	}
	
	for (int i = 1; i <= n; i++) {
		cost[i] = v[i][0];
	}

	for (int i = 1; i <= n; i++) {
		v_build[i].push_back(i);
		for(int j = 1; j < v[i].size(); j++) {
			v_build[i].push_back(v[i][j]);
		}
	}

	for (int i = 1; i <= n; i++) {
		cal_cost(i);
		fill(visited.begin(), visited.end(), 0);
	}
	
	for (int i = 1; i <= n; i++) {
		cout << re_cost[i] << endl;
	}
}

void cal_cost(int b) {
	q.push(b);
	visited[b] = 1;
	re_cost[b] += cost[b];
	while (!q.empty()) {
		int f = q.front();
		q.pop();
		for (int i = 0; i < v_build[f].size(); i++) {
			if (visited[v_build[f][i]] == 0) {
				q.push(v_build[f][i]);
				re_cost[b] += cost[v_build[f][i]];
				visited[v_build[f][i]] = 1;
			}
		}
	}
}

 

<코드>

→ 위상정렬의 진입차수 계산 방식을 이용해 문제에 접근해야 해결됨

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int n;
vector<vector<int>> A;
vector<int> indegree;
vector<int> selfbuild;
vector<int> cost;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int node;
	cin >> n;
	
	A.resize(n + 1);
	indegree.resize(n + 1);
	selfbuild.resize(n + 1, 0);
	cost.resize(n + 1, 0);
	
	for (int i = 1; i <= n; i++) {
		cin >> selfbuild[i]; // 해당 건물을 짓기 위한 시간
		for (int j = 0; j < n; j++) {
			cin >> node;
			if (node == -1) {
				break;
			}
			else {
				A[node].push_back(i);
				indegree[i]++; // 진입 차수 저장
			}
		}
	}
	
	queue<int> q;

	// 위상 정렬 수행
	for (int i = 1; i <= n; i++) {
		if (indegree[i] == 0) {
			q.push(i);
		}
	}

	while (!q.empty()) {
		int f = q.front();
		q.pop();
		for (int i = 0; i < A[f].size(); i++) {
			cost[A[f][i]] = max(cost[A[f][i]], cost[f] + selfbuild[f]);
			indegree[A[f][i]]--;
			if (indegree[A[f][i]] == 0) {
				q.push(A[f][i]);
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		cout << cost[i] + selfbuild[i] << endl;
	}
}