백준 1368 - 물대기

 

 

문제 설명

선주는 자신이 운영하는 N개의 논에 물을 대려고 한다. 물을 대는 방법은 두 가지가 있는데 하나는 직접 논에 우물을 파는 것이고 다른 하나는 이미 물을 대고 있는 다른 논으로부터 물을 끌어오는 법이다.

각각의 논에 대해 우물을 파는 비용과 논들 사이에 물을 끌어오는 비용들이 주어졌을 때 최소의 비용으로 모든 논에 물을 대는 것이 문제이다.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, N개의 논에 물을 모두 채우기 위한 최소 비용을 구해야 한다.

논에 물을 채우는 방법은 두 가지이다.

• 직접 물을 채우기
• 다른 논에서 끌어오기

두 방법은 비용이 다르다.

 

해당 문제는 문제의 표현을 살짝 바꿔보면 쉽게 풀 수 있다.

물을 직접 채우는 방식이 없다고 생각하고 무조건 다른 논에서 끌어온다고 생각해 보자.

그렇다면 최소 비용으로 모든 논을 채우기 위해서는 두 논이 최소 비용으로 연결된 간선을 선택해야 한다.

또한, 같은 논에 두 번 채우는 일은 없어야 한다.

즉, 최소 신장 트리(MST)를 만드는 것과 동일하다.

 

이제 물을 직접 채우는 것까지 고려해 보자.

물을 직접 채우는 상황은 a에서 b로 MST를 확장하는 상황에서 a → b보다 b를 직접 채우는 비용이 더 적을 때 밖에 없을 것이다.

즉, MST를 확장하는 과정에서 연결하는 비용과 직접 물을 채우는 비용을 비교하여 더 적은 것을 선택하면 된다.

 

MST를 만드는 방법은 크게 두 가지이다.

• 크루스칼 알고리즘
• 프림 알고리즘

크루스칼 알고리즘은 탐욕법을 이용하여 비용이 적은 간선부터 추가하며 사이클이 생성되는지 판단하는 알고리즘이다.

만약, 사이클이 생성된다면 해당 간선은 MST에 추가하지 않고 진행한다.

이는 Union-Find를 이용하면 쉽게 구현할 수 있다.

해당 문제에 크루스칼 알고리즘을 적용하기 위해서는 다음과 같이 처리하면 된다.

//<cost, a, b>
vector<tuple<int, int, int>> edges;

for (int i = 1; i <= N; i++)
{
    int dig;
    cin >> dig;

    //가상의 노드 0번에서 시작하여 i번에 도착하는 간선
    //= 물을 직접 채우는 작업
    edges.push_back({ dig, 0, i });
}

for (int i = 1; i <= N; i++)
{
    for (int j = 1; j <= N; j++)
    {
        int cost;
        cin >> cost;

        //i -> j로 끌어가는 간선
        //= 물을 끌어가는 작업
        if (j > i) edges.push_back({ cost, i, j });
    }
}

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

int ans = 0;
for (auto [cost, a, b] : edges)
{
    if (unite(a, b)) ans += cost;
}

unite는 a와 b를 연결하는 함수이다.

연결에 성공했다면 cost를 더해준다.

만약, 이미 연결되어 있다면(같은 컴포넌트) 무시한다.

 

두 번째 방법은 프림 알고리즘이다.

프림 알고리즘은 다익스트라와 거의 동일하다.

하나의 노드를 시작으로 연결된 최소의 간선을 선택하여 컴포넌트를 확장한다.

해당 문제에서는 이 과정에서 연결하는 비용과 직접 채우는 비용을 비교하면 된다.

long long Prim(int start, vector<long long>& costs)
{
    costs[start] = 0;

    priority_queue<pair<long long, int>> pq;
    vector<bool> visited(N, false);
    pq.push({ 0, start });

    while (!pq.empty())
    {
        auto [cost, current] = pq.top();
        pq.pop();

        if (visited[current]) continue;
        visited[current] = true;

        for (int i = 0; i < N; i++)
        {
            if (i == current) continue;
            if (visited[i]) continue;

            int dist = min(digCosts[i], dragCosts[current][i]);
            if (dist < costs[i])
            {
                costs[i] = dist;
                pq.push({-dist, i});
            }
        }
    }

    long long result = 0;
    for (int i = 0; i < N; i++)
    {
        result += costs[i];
    }

    return result + digCosts[start];
}

 

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int N;
vector<int> digCosts;
vector<vector<int>> dragCosts;
vector<long long> dp;

long long Prim(int start, vector<long long>& costs)
{
    costs[start] = 0;

    priority_queue<pair<long long, int>> pq;
    vector<bool> visited(N, false);
    pq.push({ 0, start });

    while (!pq.empty())
    {
        auto [cost, current] = pq.top();
        pq.pop();

        if (visited[current]) continue;
        visited[current] = true;

        for (int i = 0; i < N; i++)
        {
            if (i == current) continue;
            if (visited[i]) continue;

            int dist = min(digCosts[i], dragCosts[current][i]);
            if (dist < costs[i])
            {
                costs[i] = dist;
                pq.push({-dist, i});
            }
        }
    }

    long long result = 0;
    for (int i = 0; i < N; i++)
    {
        result += costs[i];
    }

    return result + digCosts[start];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(4);

    cin >> N;
    digCosts.resize(N);
    dragCosts.resize(N, vector<int>(N));
    dp.resize(N, LLONG_MAX);

    int minCost = INT_MAX;
    int start = -1;
    for (int i = 0; i < N; i++)
    {
        cin >> digCosts[i];
        if (digCosts[i] < minCost)
        {
            minCost = digCosts[i];
            start = i;
        }
    }

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> dragCosts[i][j];
        }
    }

    cout << Prim(start, dp);

    return 0;
}

---