백준 1368번: 물대기 (C++)

문제링크

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

풀이방법

해당 문제는 최소 신장 트리를 구하는 알고리즘을 사용하여 해결할 수 있다. 최소 신장 트리를 찾는 알고리즘에는 두 가지가 있다. 하나는 크루스칼 알고리즘 나머지 하나는 프림 알고리즘이다. 이 중 프림 알고리즘을 사용하여 해당 문제를 해결하였다.
다만, 이 문제를 해결하는데 가장 중요한 점은 그래프를 목적에 맞게 변형하는 것이다. 그 이유는 직접 논에 우물을 파는 경우를 그래프로 표현할 수가 없기 때문이다. 바로 방법을 알려주면 직접 논에 우물을 파는 경우를 추가적인 노드를 만들어서 추가된 노드에 가중치를 주는 방식으로 구현할 수 있다. 아래 그림을 보면 이해가 될 것이다. 5번 노드를 추가해서 해당 노드로 직접 논에 우물을 파는 가중치로 연결하였다.

위 그림을 바탕으로 최소 신장 트리의 값을 구하는 알고리즘을 적용한다. 코드는 아래와 같다.

코드

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

int n;
vector<pair<int, int>> adj[305];
// (비용, 정점 번호)
// chk[i] : i번째 정점이 최소 신장 트리에 속해있는가?
bool chk[305];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    int cost;
    for (int i = 1; i <= n; i++)
    {
        cin >> cost;
        adj[i].push_back({ cost,n+1 });
        adj[n+1].push_back({ cost,i });
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> cost;
            if (i >= j)
            adj[i].push_back({ cost,j });
            adj[j].push_back({ cost,i });
           
        }
    }

    // tuple<int,int,int> : {비용, 정점 1, 정점 2}
    priority_queue < tuple<int, int, int>, vector < tuple<int, int, int>>,greater<tuple<int, int, int>> > pq;

    chk[1] = 1;
    for (auto nxt : adj[1])
    {
        pq.push({ nxt.X,1,nxt.Y });
    }

    int cnt = 0;
    int ans = 0;
    while (cnt < n)
    {
        int cost, a, b;
        tie(cost, a, b) = pq.top(); pq.pop();
        if (chk[b]) continue;
        ans += cost;
        chk[b] = 1;
        cnt++;
        for (auto nxt : adj[b]) {
            if (chk[nxt.Y]) continue;
            pq.push({ nxt.X,b,nxt.Y });
        }
    }
    cout << ans << '\n';
    return 0;
}