1516번 게임 개발
게임에서 어떤 건물을 짓기 위해서 다른 건물을 먼저 지어야 하는 상황이 있을 수 있는데, 이 상황에서 각 건물을 건설하는데 걸리는 최소 시간을 구하는 문제이다.
생각해야 할 중요한 점은 건물들이 동시에 지어질 수 있다는 것이다.
문제 해결 전략
트리를 구성한 후 dfs를 사용하여 해결하였다.
전체 시간을 visited[] 배열을 사용하였고, 순수 해당 건물을 짓는데 걸리는 시간을 t[] 배열을 사용하였다.
dfs를 하는 과정에서 만약 해당 건물이 제일 마지막에 지어져야 할 건물이면(그 건물 뒤에 지을 건물이 없는 경우) 해당 건물의 시간에 입력받은 시간을 저장한다.
위 상황이 아니라면 건물이 동시에 지어질 수 있다고 했기 때문에 순수 해당 건물을 짓는 시간 + 이후에 지어져야 할 건물들 중 지어지는 시간이 가장 큰 시간 을 해당 건물을 짓는 총 시간에 저장하면 된다.
이후 지어져야 할 건물들의 시간은 만약 시간이 이미 구해졌다면 그 시간을 사용하면 되고, 아직 구해지지 않았다면 dfs를 통해 시간을 구하면 된다.
그리고 각각 걸리는 시간을 누적해야 하기 때문에 dp를 사용한다.
코드
#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> v[501];
int t[501];
int visited[501];
int dfs(int x){
if(v[x].size() == 0) {
visited[x] = t[x];
return t[x];
}
int tmp = 0;
for(int i=0;i<v[x].size();i++)
{
if(visited[v[x][i]] != 0)
tmp = max(tmp,visited[v[x][i]]);
else
tmp = max(tmp,dfs(v[x][i]));
}
visited[x] = tmp + t[x];
return visited[x];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> t[i];
for(int j=0;;j++)
{
int x;
cin >> x;
if(x == -1)
break;
v[i].push_back(x);
}
}
for(int i=1;i<=n;i++)
cout << dfs(i) << "\n";
return 0;
}생각해볼 점
위 문제를 해결하고 난 뒤 알고리즘 분류를 확인해 보니 위상정렬 문제였다.
모든 건물들을 순서에 맞게 지어야 하기 때문에 위상정렬을 쓰는 것이다.
그래서 위상정렬을 통해 새롭게 풀어 보았다.
문제 해결 전략2
그래프를 생성함에 있어 탐색은 가장 마지막에 지어지는 건물부터 해야 하기 때문에 dfs를 사용했을 때와 반대 방향으로 그래프를 생성해 준다.
전체 시간을 ti[] 배열에, 순수 시간을 t[] 배열에 저장하였다.
또한 위상정렬을 사용하기 위해 ind[] 배열에 부모의 수를 저장한다.
부모가 없는 경우가 마지막에 지어지는 건물이므로 해당 건물들의 자식노드들에 대해 탐색을 진행한다.
동시에 지어질 수 있는 상황이므로 해당 건물의 전체 시간에 이미 정해져 있던(누적된) 시간과 순수시간 + 자식이 지어지는 전체 시간 중 더 큰 값을 저장하여 계속 누적한다.
코드
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n;
vector<int> v[501];
int t[501];
int ind[501];
int ti[501];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> t[i];
for(int j=0;;j++)
{
int x;
cin >> x;
if(x == -1)
break;
v[x].push_back(i);
ind[i]++;
}
}
queue<int> q;
for(int i=1;i<=n;i++){
if(ind[i] == 0){
q.push(i);
ti[i] = t[i];
}
}
while(!q.empty()){
int x = q.front();
q.pop();
for(int i=0;i<v[x].size();i++){
ind[v[x][i]]--;
ti[v[x][i]] = max(ti[v[x][i]],t[v[x][i]] + ti[x]);
if(ind[v[x][i]] == 0){
q.push(v[x][i]);
}
}
}
for(int i=1;i<=n;i++)
cout << ti[i] << "\n";
return 0;
}
결과 중 위의 결과가 위상정렬을, 아래의 결과가 dfs를 사용한 결과이다.
시간이 두배 정도 차이나는 것을 확인할 수 있는데, dfs를 사용했을 경우 가장 깊이 내려갈 때와 올라올 때 총 두번 노드를 방문하는 반면, 위상정렬의 경우 맨 아래에서 올라오는 경우만 하므로 한번만 노드를 방문하게 된다.
아마 위의 차이 때문에 시간이 두배 정도 차이가 나는것 같다.
