[BOJ] 1516 게임 개발(DFS+DP or 위상 정렬+DP)

www.acmicpc.net/problem/1516

1516번: 게임 개발

주제: DFS+DP or 위상정렬+DP

시간복잡도: O(|V| + |E|)

 

1) DFS, DP를 이용한 풀이(8ms, 간단함)

설명:

재귀 함수를 이용해서 TOP- DOWN 형식으로 DFS를 돌며 Critical Path(동시에 실행할 때 제일 시간이 오래 걸리는 경로)가 걸리는 시간을 구해낸다.

 

기준 노드로 들어오는 경로 중에서 가장 오래걸리는 경로를 선택한다. 즉, 다익스트라의 최대값 구하기 버전으로 생각해도 무방하다. 

 

#include<bits/stdc++.h>

using namespace std;

vector<int> v[501];
int longest_cost[501];
int cost[501];
int N;

int dfs(int now)
{
	int size = v[now].size();
	
	int big = 0;
	for(int i = 0; i < size; i++)
	{
		int x = v[now][i];
		if(longest_cost[x] == 0)
		{
			longest_cost[x] = dfs(x);	
		} 
		
		big = max(big, longest_cost[x]);
	}
	
	return cost[now] + big;
}

int main()
{
	//scanf를 쓸 거면 지운다  
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> N;
	
	int tmp;
	for(int i = 1; i <= N; i++)
	{
		cin >> tmp;
		cost[i] = tmp;
		
		while(1)
		{
			cin >> tmp;
			if(tmp == -1) break;
			
			v[i].push_back(tmp);
		}
	}
	
	
	for(int i = 1; i <= N; i++)
	{
		cout << dfs(i) << '\n';
	}
	
	return 0;
}

 

2) 위상정렬, DP를 이용한 풀이(4ms, 비교적 어려움) 

설명: 

만약, 위상정렬에 대해서 모른다면, 찾아보도록 하자.

위상정렬을 간단히 말하면 그래프 노드들의 실행 순서를 결정하는 알고리즘이다.

글쓴이는 동빈나 알고리즘 수업으로 위상정렬을 공부했다.

m.blog.naver.com/ndb796/221236874984

25. 위상 정렬(Topology Sort)

위상정렬을 이용해서 DOWN-TOP 형식으로, 초기 진입차수가 0인 노드들로부터 시작해서 차근차근 연결된 노드들에 도달할 때 걸리는 최대 시간을 갱신해간다. 아래 코드가 최대 시간을 갱신하는 부분이다. 사실상 다익스트라처럼 구현하면 된다. 

int next = v[now][i];
if(dp[next] < dp[now] + node[next])
{
    dp[next] = dp[now] + node[next];
}

 

전체 코드:

#include<bits/stdc++.h>

using namespace std;

int N;
int node[501];
int inDegree[501];
int dp[501];
vector<int> v[501];

void topologySort()
{
	queue<int> q;
	
	for(int i = 1; i <= N; i++)
	{
		if(inDegree[i] == 0)
		{
			q.push(i);
			dp[i] = node[i];	
		}	
	}	
	
	while(!q.empty())
	{
		int now = q.front();
		q.pop();
		
		int size = v[now].size();
		for(int i = 0; i < size; i++)
		{
			int next = v[now][i];
			if(dp[next] < dp[now] + node[next])
			{
				dp[next] = dp[now] + node[next];
			}
			
			if(--inDegree[next] == 0)
			{
				q.push(next);
			}
		}
	}
	
	for(int i = 1; i <= N; i++)
	{
		cout << dp[i] << '\n';
	}
}

int main()
{
	//scanf를 쓸 거면 지운다  
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> N;
	
	int tmp;
	for(int i = 1; i <= N; i++)
	{
		cin >> tmp;
		node[i] = tmp;
		
		while(1)
		{
			cin >> tmp;
			if(tmp == -1) break;
			
			v[tmp].push_back(i);
			inDegree[i]++;
		}
	}	
	
	topologySort(); 

	return 0;
}

 

고찰:

이 문제는 2가지 방식으로 풀 수 있었다. dfs+dp 또는 위상정렬+dp로 말이다. 일반적인 dp를 생각했을 때,

down-top 방식이 top-down 방식보다 빠르기 때문에, 위상정렬+dp 방식(4ms)이 dfs+dp 방식(8ms)보단 빨랐던 것 같다.

일반적으로, 선행 프로세스(노드)가 존재하는 그래프에서는 위상 정렬을 통해 프로세스의 실행 순서를 결정해줘야 한다.  

 

주의해야 할 점이라면, 

이 문제의 가장 중요한 조건인 '여러 개의 건물을 동시에 지을 수 있다' 를 놓치면, 단순한 dfs 경로 누적합 문제로 귀결시킬 수 있다. 동시에 지을 수 있기 때문에, critical path를 찾는 것이 중요 포인트였다.

 

또한, dfs+dp와 위상정렬+dp는 그래프 탐색 시, 이동하는 방향이 반대이기 때문에, 인접리스트에 연결 노드를 입력할 때 반대 방향으로 넣어야 한다. 

ex)

dfs+dp : v[i].push_back(tmp);

위상정렬 + dp : v[tmp].push_back(i);