[백준 1368] 물대기 (C++)

1368번: 물대기

 

모든 논을 최소 비용으로 연결시키는 문제이다.

따라서 최소 스패닝 트리라고 생각할 수 있다.

 

 

문제의 핵심은 이미 물이 있는 논을 통해서만 물을 댈 수 있다는 것이다.

 

그래서 어렵게 생각한다면 우물을 파는데 가장 비용이 적은 논을 구하고..

그 논을 통해서 가장 비용이 적은 간선을 선택하고..

등등

케이스가 복잡한 상황이 정말 많이 생길 것이다

 

 

다익스트라에서 주로 사용했었던 방식인데 가상 노드를 하나 설정한다.

가상 노드는 논들과 연결된다.

이때 가상 노드와 논을 연결하는 간선의 비용은 논에서 우물을 파는 비용으로 설정하면 된다.

그리고 나머지는 논과 논을 연결하는 비용들로 그래프를 구성할 수 있다.

 

가상노드와 논을 연결하는 간선들이 있기 때문에 MST 알고리즘 특성상

반드시 해당 간선을 하나라도 포함할 수 밖에 없다. -> 우물을 파는 논이 자연스레 생긴다.

 

그래서 위에서 어렵게 생각했던 부분을 단번에 해결할 수 있게 된다.

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
struct Edge{
    int src;
    int dst;
    int cost;
};
 
bool cmp(Edge &a, Edge &b){
    return a.cost < b.cost;
}
 
int N, ans = 0;
int non_cost[301];
vector<Edge> paddy;
int node[301];
 
void input(){
    int c;
    
    cin >> N;
    for(int i = 1; i <= N; i++){
        cin >> non_cost[i];
    }
    
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            cin >> c;
            Edge newEdge;
            if(i == j){
                newEdge.src = 0;
                newEdge.dst = i;
                newEdge.cost = non_cost[i];
            }
            else{
                newEdge.src = i;
                newEdge.dst = j;
                newEdge.cost = c;
            }
            paddy.push_back(newEdge);
        }
    }
    
    memset(node, -1, sizeof(node));
}
 
int findtopnode(int a){
    if(node[a] < 0) return a;
    return node[a] = findtopnode(node[a]);
}
 
bool Union_Node(int a, int b){
    a = findtopnode(a);
    b = findtopnode(b);
    
    if(a == b) return false;
    
    if(node[a] < node[b]){
        node[a] += node[b];
        node[b] = a;
    }
    else{
        node[b] += node[a];
        node[a] = b;
    }
    return true;
}
 
void solve(){
    sort(paddy.begin(), paddy.end(), cmp);
    
    int nodeCnt = 0;
    
    for(int i = 0; i < paddy.size(); i++){
        int u = paddy[i].src;
        int v = paddy[i].dst;
        int c = paddy[i].cost;
        if(Union_Node(u, v)) ans += c;
    }
    
    cout << ans;
}
 
int main(){
    fastio
    input();
    solve();
    
    return 0;
}