백준/1368/MST/물대기

백준/1368/MST/물대기
MST로 해결 가능할거 같은 문제인데 논 자체를 파야되는 값을 어떻게 처리해줄지가 고민이었습니다.
제일 먼저 떠올린 생각은 논 자체를 파는 값은 스스로에게로 돌아가는 방법입니다.

그러나 이 방법을 사용하게 되면 스패닝 트리 자체가 성립이 되지 않기 때문에 다른 방법을 생각하였습니다.

저 생각에서 좀 더 생각해보니 다른 한 점을 추가하여 해당 노드들로 간선을 이어주면 추가한 점으로부터 다른 노드까지의 간선으로 스스로 논을 파는 값을 처리해줄수가 있었습니다.

int main()
{
	cin>>V;
    int cost;
    int v=V+1;
    for(int i=0;i<V;i++)
    {
        int u=i;
        cin>>cost;
        edge[count1]=tie(cost,u,v);
        count1++;
    }
    for(int i=0;i<V;i++)
    {
        for(int j=0;j<V;j++)
        {
            cin>>cost;
            if(i<j)
            {
               edge[count1]=tie(cost,i,j);
               count1++;
            }
        }
    }
}

값을 넣어주는 방법만 해결하고 나머지는 크루스칼 알고리즘을 활용하여 해결하였습니다.

풀이

1. 첫번째 풀이

#include<iostream>
#include<vector>
#include<tuple>
#include<algorithm>
using namespace std;

void solution();
void solve();

vector<int>p(305,-1);
tuple<int,int,int>edge[100005];
int V;
int count1,result;

int getParent(int num)
{
    if(p[num]<0)return num;
    return getParent(p[num]);
}

bool union_find(int u,int v)
{
    u=getParent(u); v=getParent(v);
    if(u==v)return 0;
    if(u>v)p[u]=v;
    else p[v]=u;
    return 1;
}

void solve()
{
    int line=0;
    sort(edge,edge+count1);
    for(int i=0;i<count1;i++)
    {
        int cost,u,v;
        tie(cost,u,v)=edge[i];
        if(!union_find(u,v))continue;
        result+=cost;
        line++;
        if(line==V)break;
    }
    solution();
}

void solution()
{
    cout<<result;
}

int main()
{
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    
    cin>>V;
    int cost;
    int v=V+1;
    for(int i=0;i<V;i++)
    {
        int u=i;
        cin>>cost;
        edge[count1]=tie(cost,u,v);
        count1++;
    }
    for(int i=0;i<V;i++)
    {
        for(int j=0;j<V;j++)
        {
            cin>>cost;
            if(i<j)
            {
               edge[count1]=tie(cost,i,j);
               count1++;
            }
        }
    }
    
    solve();
}