백준 1368번 - 물대기

https://www.acmicpc.net/problem/1368

1368번: 물대기

 

 

• 필요한 배경지식

최소 신장 트리 : Minimum Spanning Tree - 크루스칼(Kruskal) 알고리즘

 

 

 

• 문제 해결 방법

MST를 활용하여 풀어낼 수 있는 문제입니다.

i번째 논과 j번째 논을 연결하는데 드는 비용 Pi,j를 그래프의 간선으로 표현하면, 문제의 조건에서 Pi,j = Pj,i 라는 것을  확인할 수 있으므로 N개의 논은 무방향 그래프로 나타낼 수 있습니다.

 

그렇다면 출력해야 할 값은 모든 노드를 연결하는데 필요한 최소비용을 의미하므로 최소 스패닝 트리를 이용하여 답을 구할 수 있습니다.

 

주의해야 할 부분은 처음에 물을 대려면 우물을 파야 하는데 이때 각 논마다 우물을 파는 비용이 따로 존재하기 때문에 이 비용을 최소비용에 고려해주어야 한다는 것입니다.

복잡하게 생각할 필요없이 우물을 하나의 다른 노드로 인식하면 문제를 쉽게 해결할 수 있습니다.

 

우물을 0번 노드라고 하면, 문제에서의 <예제 입력1>의 최소 스패닝 트리는 아래와 같습니다.

 

예제입력1의 최소 스패닝 트리

 

 

 

 

• C++ 전체 코드

#include<bits/stdc++.h>
using namespace std;
using tpi = tuple<int,int,int>;

int N,M;
int parent[301]{};
vector<tpi> edge;

// Union-Find
int find(int k) {
​​​​if (k == parent[k]) return k;
​​​​else return parent[k] = find(parent[k]);
}
void merge(int a, int b) {
​​​​a = find(a);
​​​​b = find(b);
​​​​parent[a] = b;
}

int main() {
​​​​ios_base::sync_with_stdio(0);
​​​​cin.tie(0);
​​​​cin>>N;
​​​​int t;
​​​​for(int i=1; i<=N; i++) {
​​​​​​​​cin>>t;
​​​​​​​​edge.push_back({t,0,i}); // 우물과 [1,N]노드들과 연결된 간선
​​​​​​​​parent[i] = i;
​​​​}
​​​​for(int i=1; i<=N; i++){
​​​​​​​​for(int j=1; j<=N; j++){
​​​​​​​​​​​​cin>>t;
​​​​​​​​​​​​if(i<j) edge.push_back({t,i,j}); // Pi,j == Pj,i 이므로
​​​​​​​​}
​​​​}
​​​​sort(edge.begin(), edge.end());

​​​​int ans = 0;
​​​​// 크루스칼
​​​​for(auto v : edge){
​​​​​​​​int w,a,b;
​​​​​​​​tie(w,a,b) = v;
​​​​​​​​if(find(a)==find(b)) continue;
​​​​​​​​merge(a,b);
​​​​​​​​ans += w;
​​​​}

​​​​cout<<ans;    
}