백준 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;    
}