백준 10021 - Watering the Fields

 

문제 설명

Due to a lack of rain, Farmer John wants to build an irrigation system to send water between his N fields (1 <= N <= 2000).

Each field i is described by a distinct point (xi, yi) in the 2D plane, with 0 <= xi, yi <= 1000. The cost of building a water pipe between two fields i and j is equal to the squared Euclidean distance between them:

(xi - xj)^2 + (yi - yj)^2

FJ would like to build a minimum-cost system of pipes so that all of his fields are linked together -- so that water in any field can follow a sequence of pipes to reach any other field.

Unfortunately, the contractor who is helping FJ install his irrigation system refuses to install any pipe unless its cost (squared Euclidean length) is at least C (1 <= C <= 1,000,000).

Please help FJ compute the minimum amount he will need pay to connect all his fields with a network of pipes.

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, N개의 농장이 모두 연결되게 파이프를 설치할 때 최소비용을 구하는 것이다.

두 농장 사이의 거리는 $(xi-xj)^2 + (yi-yj)^2$로 나타낸다.

단, C이하의 파이프는 설치할 수 없다.

 

즉, MST를 만드는 것이다.

MST를 만들기 위해서는 각 농장끼리의 간선이 필요하다.

이 문제에서는 거리가 C이상인 모든 농장을 연결할 수 있다.

 

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

크루스칼 알고리즘, 프림 알고리즘이다.

크루스칼 알고리즘은 탐욕법 기반으로 가장 작은 간선을 선택하며 MST를 만든다.

따라서, 모든 농장끼리 간선을 미리 계산하여 정렬하는 과정이 필요하다.

또한, 효율적 계산을 위해 유니온-파인드 자료 구조와 연산을 만들어야 한다.

 

프림 알고리즘은 다익스트라와 유사하게 포함된 농장을 통해 연결가능한 농장들을 늘려가며 MST를 만든다.

즉, 우선순위큐 하나로 구현이 가능하다.

따라서, 프림 알고리즘을 선택했다.

 

문제 해결은 간단하다.

1. 임의의 농장을 포함하고 다른 농장까지의 거리를 구해 우선순위 큐에 넣는다.(가까운 순으로 정렬)
2. 우선순위 큐에서 하나의 농장을 뽑아 또 다른 농장과 연결한다.

위 과정을 그림으로 나타내면 다음과 같다.

초기에는 위와 같은 상태이다.

1번 농장과는 29, 2번 농장과는 17의 비용이 든다.

두 비용 모두 11(C)이상이므로 연결 가능하다.

두 농장을 우선순위 큐에 넣은 뒤 다음 과정을 진행한다.

우선순위 큐에 의해 더 적은 비용(17)이 드는 2번 농장과 연결된다.

이후, 2번 농장과 1번 농장 사이 비용은 10으로 11(C) 보다 적어 연결이 불가능하다.

위의 과정을 반복하면 다음과 같은 상황이 된다.

 

이때, 주의할 점은 모든 농장을 연결할 수 없는 상황이 있을 수 있다.

모든 농장사이의 거리가 C이하인 농장이 존재하는 경우이다.

그럴 경우에는 해당 농장이 우선순위 큐에 들어갈 수 없다.

따라서, 방문 여부를 체크하여 해결할 수 있다.

for (int i = 0; i < N; i++)
{
    if (!visited[i])
    {
        cout << -1;
        return 0;
    }
}

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <set>

using namespace std;

int N, C;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> C;

    vector<pair<int, int>> farms;
    vector<bool> visited(N, false);
    int answer = 0;

    for (int i = 0; i < N; i++)
    {
        int y, x;
        cin >> y >> x;
        farms.push_back({ y,x });
    }

    //MST
    priority_queue<pair<int, int>> pq;
    pq.push({ 0,0 });

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

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

        dist *= -1;
        answer += dist;

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

            int d = (farms[i].first - farms[idx].first) * (farms[i].first - farms[idx].first) + (farms[i].second - farms[idx].second) * (farms[i].second - farms[idx].second);
            if (d < C) continue;

            pq.push({ -d, i });
        }
    }

    for (int i = 0; i < N; i++)
    {
        if (!visited[i])
        {
            cout << -1;
            return 0;
        }
    }

    cout << answer;

	return 0;
}

---