[BOJ / 위상정렬] 1516 게임개발

www.acmicpc.net/problem/1516

1516번: 게임 개발

 

1516 게임개발

 

알고리즘 : 위상정렬, 우선순위큐

전체적으로 풀면서 다익스트라 느낌이 드는 문제였습니다.

다익스트라와 위성정렬 문제를 풀어본 적이 있다면 쉽게 풀이할 수 있습니다.

위상정렬로 inDegree가 0인 아이들만 우선순위 큐에서 관리하면 됩니다.

 

 

 

< CODE >

#include <iostream>
#include <algorithm>
#include <climits>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <string.h>
#include <cstdlib>

using namespace std;

#define MAX 505

vector<int> child[MAX];
int inDegree[MAX];
int timer[MAX];
int dp[MAX];

struct mQ
{
	int v;
	int t;
	
	mQ(int a, int b)
	{
		v = a;
		t = b;
	}
};

priority_queue<mQ> pq;

bool operator<(const mQ & a, const mQ & b)
{
	if(inDegree[a.v] == inDegree[b.v])
	{
		if(a.v == b.v)
			return a.t > b.t;
		
		return a.t > b.t;
	}
	
	return inDegree[a.v] < inDegree[b.v];
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int n;
	
	cin >> n;
	
	for(int i = 1; i <= n; i++)
	{
		cin >> timer[i];
		
		int par;
		
		while(cin >> par)
		{
			if(par == -1)
				break;
			
			child[par].push_back(i);
			inDegree[i]++;
		}
	}
	
	for(int i = 1; i <= n; i++)
	{
		if(inDegree[i] == 0)
		{
			pq.push(mQ(i,timer[i]));
			dp[i] = timer[i];			
		}
	}
	
	while(!pq.empty())
	{
		mQ cur = pq.top(); pq.pop();
		
		if(cur.t < dp[cur.v])
			continue;
		
		for(int i = 0; i < child[cur.v].size(); i++)
		{
			int c = child[cur.v][i];
			int cost = cur.t + timer[c];
			
			inDegree[c]--;
			
			if(inDegree[c] == 0 && dp[c] < cost)
			{
				dp[c] = cost;
				pq.push(mQ(c, cost));				
			}
		}
	}
	
	for(int i = 1; i <= n; i++)
		cout << dp[i] << '\n';
	
	return 0;
}

시간 : 4ms

 

태그 : #boj 1516 #boj 게임개발 #1516 게임개발 #위상정렬 #우선순위큐 #알고리즘