[C++/백준] 1368번: 물대기*

문제 링크

1368번: 물대기

 

풀이

최소 신장 트리인데 그래프 변형이 필요한 문제
어찌됐든 하나의 논에는 우물을 파야하기 때문에 노드를 하나 추가해서 (나같은 경우는 0번 노드) 각 우물을 파는 경우까지 최소 신장 트리로 구한다.
나머지는 크루스칼 알고리즘으로 union-find를 사용하면 여느 최소 신장 트리 문제와 비슷하다.

 

코드

#include <iostream>
#include <queue>
#include <vector>
#include <tuple>
#include <algorithm>

using namespace std;

int find(int node, vector<int>& parent)
{
    if (node == parent[node])
    {
        return node;
    }
    else
    {
        return parent[node] = find(parent[node], parent);
    }
}

void union_find(int stt, int end, vector<int>& parent)
{
    int parS, parE;
    parS = find(stt, parent);
    parE = find(end, parent);
    if (parS > parE)
    {
        parent[parS] = parE;
    }
    else
    {
        parent[parE] = parS;
    }
}

int main()
{
    int n;
    cin >> n;

    vector<tuple<int, int, int>> v; // 비용, 시작, 끝
    for (int i = 1; i <= n; i++)
    {
        int tmp;
        cin >> tmp;
        v.push_back(make_tuple(tmp, 0, i));
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            int tmp;
            cin >> tmp;
            if (i == j) continue;
            v.push_back(make_tuple(tmp, i, j));
        }
    }

    sort(v.begin(), v.end());

    vector<int> parent(n + 1);
    for (int i = 0; i <= n; i++)
    {
        parent[i] = i;
    }

    int answer = 0;
    for (int i = 0; i < v.size(); i++)
    {
        int cost, stt, end;
        tie(cost, stt, end) = v[i];
        if (find(parent[stt], parent) != find(parent[end], parent)) // 부모 노드가 다르면
        {
            union_find(stt, end, parent);
            answer += cost;
        }
    }

    cout << answer;
}