유럽여행
문제 해석
N개의 나라를 여행하는데 드는 최소 비용을 구하는 문제입니다.
N개의 나라들 사이에 이동가능한 길이 M개 있고 각각 통과료가 있습니다.
N개의 나라 별로 드는 비용이 있습니다.
설계(40)
MST문제인 것을 알고 접근했는데도 생각하기 어려웠던 문제였습니다.
N-1개의 길만 남겨야하므로 MST를 이용하는데, 생성가능한 모든 경우를 보면 시작나라를 제외한 모든 나라는 두번 방문을 합니다.
모든 나라를 두번 방문하기 때문에 각 연결된 간선을 두번씩 방문한다는 뜻입니다.
u->v로 이동하는 최종 비용을 구하기 위해서는 (u의 비용 + v의 비용 + u와 v 사이의 길 통과료x2) 가 됩니다.
또 다른 특이한 점은 시작 나라를 선정해야 하기 때문에 시작나라는 한번 더 방문을 해야한다는 점입니다.
따라서 모든 나라 중 최소 비용인 나라를 선택해서 방문하도록 합니다.
구현(10)
코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define MAXN 10001
int par[MAXN];
int W[MAXN];
struct node{
int u,v,w;
bool operator <(const node& a)const{
return w < a.w;
}
};
int N,M;
vector<node> adj;
int Find(int x){
if (!par[x]) return x;
return par[x] = Find(par[x]);
}
bool Merge(int u, int v){
u = Find(u);
v = Find(v);
if (u == v) return false;
par[v] = u;
return true;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M;
int ans = 1000;
for (int i = 1 ;i <=N; i++){
cin >> W[i];
ans = min(ans,W[i]);
}
for (int i = 0 ;i <M; i++){
int u,v,w;
cin >> u >> v >> w;
adj.push_back({u,v,w*2+W[u]+W[v]});
}
sort(adj.begin(),adj.end());
for (int i = 0 ;i < adj.size(); i++){
if (Merge(adj[i].u,adj[i].v)) ans+=adj[i].w;
}
cout << ans <<"\n";
return 0;
}
디버깅
제출결과
32 ms
마무리
MST알고리즘을 응용한 문제였습니다.
구현은 어렵지 않지만 가중치를 설정하는 아이디어가 필요했던 문제였습니다.