📝 문제 정보
🧐 관찰 및 접근
- 집 (정점)과 길 (간선)이 있다.
- 마을 두개로 분리해야한다.
- 이 때, 간선의 가중치의 합을 최소화해야한다.
- 마을 두개로 분리해야한다.
- 이미 두 집이 한 마을 안에 있다면, 둘이 연결할 필요가 없다.
- 이미 다른 우회로로 갈 수 있기 때문
- 연결하던 도중 마을이 두개가 남았다면 끝내면 된다.
- 크루스칼 알고리즘으로 덩어리가 두개가 남을때까지 반복하면 되겠다.
💻 풀이
- 코드 (C++):
void solve(){
int N, M; cin >> N >> M;
vector<tuple<int, int, int>> edges; // weight, u, v
rep(i, 0, M){
int u, v, w; cin >> u >> v >> w;
edges.emplace_back(w, u, v);
}
UF.init(N+1);
sort(all(edges));
int ans = 0;
for(auto &[w, u, v]: edges){
if(UF.group == 3) break;
if(UF.merge(u, v)) ans += w;
}
cout << ans << "\n";
}