백준 Gold 3 ACM Craft
ACM Craft (백준 Gold 3)
https://www.acmicpc.net/problem/1005
주어지는 건물의 비용과 건물의 ‘테크트리’가 주어졌을 때
특정 건물 w를 짓는데 걸리는 최소 시간
접근 방법
일단 ‘건물’의 ‘지어지는 순서’가 존재하며
앞선 테크가 전부 지어지지 못하면
뒷 건물을 개발할 수 없기에
각 노드의 ‘연결’과 ‘그 연결 개수’가 중요한
‘위상정렬’문제라 판단할 수 있었다
-
각 간선은 ‘방향’을 갖고
그 방향이 ‘가리켜진’ 노드는 차수가 하나 늘어난다 -
목표 노드의 ‘지어지는 시간’ 중에서
‘가장 짧은 것’을 찾아야 하나
결국 해당 노드와 ‘연결’된 차수 들이
‘먼저 선행’되어야 지을 수 있음 -
모든 노드는 ‘동시에’ 지어질 수 있다
따라서 제작 시간이 ‘긴’ 노드가 지어지는 중
가능한 다른 노드의 제작 시간이 진행될 수 있음 -
- ‘최소 작업시간’ 힙을 이용한 접근
- 작업 시간이 빨리 끝나는 순서로 ‘힙’이 정렬되고
degree가 0이 된 순간 ‘힙’에 들여보내기에
nowTime은 ‘이미 선행 작업들이 완료된 시간’을 포함
(degree : 0 - 더 이상 선행할 작업 없음)
- ‘최소 작업시간’ 힙을 이용한 접근
제출 코드 - 오답
#include<iostream>
#include<vector>
#include<unordered_map>
#include<queue>
#include<limits.h>
using namespace std;
struct node
{
int idx; // 노드 번호
int value; // 비용
int degree; // 차수
vector<int> next;
};
typedef pair<int, int> pii;
struct Compare
{
bool operator()(const pii& a, const pii& b)
{
return a.second > b.second;
}
};
int func(int start, int to, unordered_map<int, node>& nodemap)
{
if (start == to)
return nodemap[start].value;
// 차수가 0인 녀석을 queue에 넣음
priority_queue<pii, vector<pii>, Compare> pq;
pq.push({ start, nodemap[start].value });
int nowTaskTime = 0;
while (pq.empty() == false)
{
int now = pq.top().first;
int nowTime = pq.top().second;
pq.pop();
if (now == to)
{
return nowTime;
}
// 그냥 다음 녀석과 다음 시간을 넣어주면 됨
// 어차피 시간이 작은 녀석이 먼저 q 앞에 오고
// 차수가 0인 녀석만 넣어줄거니 자동으로 뒷 시간에 맞춰짐
for (int next : nodemap[now].next)
{
nodemap[next].degree--;
if (nodemap[next].degree <= 0)
{
pq.push({ next,nodemap[next].value + nowTime });
}
}
}
return INT_MAX;
}
int main()
{
int t;
cin >> t;
while (t > 0)
{
t--;
int n, k;
cin >> n >> k;
unordered_map<int, node> nodemap;
for (int i = 1; i <= n; i++)
{
nodemap[i].idx = i;
cin >> nodemap[i].value;
}
for (int i = 0; i < k; i++)
{
int start, to;
cin >> start >> to;
nodemap[start].next.push_back(to);
nodemap[to].degree++;
}
int to;
cin >> to;
vector<int> starts;
for (auto& p : nodemap)
{
if (p.second.degree == 0)
{
starts.push_back(p.first);
}
}
int mV = INT_MAX;
for (int s : starts)
{
mV = min(mV, func(s, to, nodemap));
}
cout << mV << '\n';
}
return 0;
}
코드 해설
pair<int,int>를 이용하여
노드 idx 및 소모 시간을 (소모시간 최소) 힙 큐에 넣어 진행하였다
-
node 구조체를 이용하여
각 노드의 idx, 비용, 다음 간선 등을 관리 -
다음 간선을 바로 힙 큐에 넣어주는 것이 아니라
차수를 ‘빼고’ 그 이후
차수가 0이된 경우 큐에 넣어준다 -
이후 마지막의 목적지 값을 출력
틀린 이유
1
5 4
10 50 10 20 10
2 1
3 1
4 3
5 4
1
- 정답은 60
위와 같이
‘목적지’에 도달하는 시작점이 여러개 존재할때
func()에 & 로 인하여 map 데이터가 더럽혀진 경우가 발생할 수 있었다
(처음에 50에서 시작했는데 1로 가니 degree가 1 남아있어서 failed)
따라서 차수가 0인 녀석들을 ‘모두’ func에서 처리할 수 있도록
코드를 수정해주었다
최종 제출 코드
#include<iostream>
#include<vector>
#include<unordered_map>
#include<queue>
#include<limits.h>
using namespace std;
struct node
{
int idx; // 노드 번호
int value; // 비용
int degree; // 차수
vector<int> next;
};
typedef pair<int, int> pii;
struct Compare
{
bool operator()(const pii& a, const pii& b)
{
return a.second > b.second;
}
};
int func(vector<int>& starts, int to, unordered_map<int, node>& nodemap)
{
// 차수가 0인 녀석을 queue에 넣음
priority_queue<pii, vector<pii>, Compare> pq;
unordered_map<int, int> dp;
for (int start : starts)
{
if (start == to)
return nodemap[start].value;
pq.push({ start, nodemap[start].value });
}
while (pq.empty() == false)
{
int now = pq.top().first;
int nowTime = pq.top().second;
pq.pop();
if (now == to)
{
return nowTime;
}
for (int next : nodemap[now].next)
{
nodemap[next].degree--;
if (nodemap[next].degree <= 0)
{
pq.push({ next,nodemap[next].value + nowTime });
}
}
}
return -1;
}
int main()
{
int t;
cin >> t;
while (t > 0)
{
t--;
int n, k;
cin >> n >> k;
unordered_map<int, node> nodemap;
for (int i = 1; i <= n; i++)
{
nodemap[i].idx = i;
cin >> nodemap[i].value;
}
for (int i = 0; i < k; i++)
{
int start, to;
cin >> start >> to;
nodemap[start].next.push_back(to);
nodemap[to].degree++;
}
int to;
cin >> to;
vector<int> starts;
for (auto& p : nodemap)
{
if (p.second.degree == 0)
{
starts.push_back(p.first);
}
}
cout << func(starts, to, nodemap) << '\n';
}
return 0;
}
결과
위상정렬은 매우 까다로운 문제 계열인 듯하다
개인적으로는 힙큐를 사용한 방식을 사용하였지만
dfs,bfs, dp 등을 이용하는 방법도 존재한다
- 일반적으로는 Kahn 위상정렬 + dp 풀이방법이라 한다
점화식
finish[start] = cost[start]
finish[v] = max(u->v{finish[u]}) + cost[v]
코드 예시)
vector<int> indeg(n+1);
vector<vector<int>> g(n+1);
vector<int> cost(n+1);
vector<int> finish(n+1, 0);
// indeg, g, cost 채워놓고…
queue<int> q;
for (int i=1;i<=n;i++)
{
if (indeg[i]==0)
{
finish[i]=cost[i];
q.push(i);
}
}
while(!q.empty())
{
int u=q.front(); q.pop();
for(int v: g[u])
{
finish[v]=max(finish[v], finish[u]+cost[v]);
if(--indeg[v]==0)
q.push(v);
}
}
// 목표 to의 최소 완료시각은 finish[to]
댓글남기기