백준 10021번 [Watering the Fields](C++) -yes6686- 티스토리

백준 문제 풀이: 10021 [Watering the Fields]

---

문제 링크: https://www.acmicpc.net/problem/10021

문제 설명:

농장의 각 좌표에서 물을 대기 위해 필요한 간선의 비용과 조건을 고려하여 최소 스패닝 트리를 구성하는 문제입니다. 다음 조건이 적용됩니다:

• 간선의 비용은 두 점 사이의 거리의 제곱으로 계산됩니다.
• 간선의 비용은 주어진 최소 거리 c 이상이어야 합니다.
• 모든 점이 연결될 수 없을 경우 -1을 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;

int parent[2001]; // 부모 배열
pair<int, int> arr[2001]; // 좌표를 저장할 배열
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> pq;

int findParent(int x) {
    if (parent[x] == x) return x;
    return parent[x] = findParent(parent[x]);
}

void unionParent(int a, int b) {
    a = findParent(a);
    b = findParent(b);
    if (a < b) parent[b] = a;
    else parent[a] = b;
}

bool isSameParent(int a, int b) {
    return findParent(a) == findParent(b);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, c; // 점의 개수와 최소 거리 제곱
    cin >> n >> c;

    // 부모 배열 초기화
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }

    // 점의 좌표 입력
    for (int i = 1; i <= n; i++) {
        cin >> arr[i].first >> arr[i].second;
    }

    // 모든 간선의 비용 계산 및 우선순위 큐에 삽입
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            int dist = pow(arr[i].first - arr[j].first, 2) + pow(arr[i].second - arr[j].second, 2);
            pq.push({dist, {i, j}});
        }
    }

    int ans = 0; // 총 비용
    int cnt = 0; // 연결된 간선의 수

    // 크루스칼 알고리즘으로 최소 스패닝 트리 구성
    while (!pq.empty()) {
        int cost = pq.top().first;
        int a = pq.top().second.first;
        int b = pq.top().second.second;
        pq.pop();

        if (!isSameParent(a, b) && cost >= c) {
            unionParent(a, b);
            ans += cost;
            cnt++;
        }
    }

    // 모든 점이 연결되지 않은 경우 -1 출력
    if (cnt == n - 1) {
        cout << ans << '\n';
    } else {
        cout << -1 << '\n';
    }

    return 0;
}

---

코드 설명

• 핵심 알고리즘: 크루스칼 알고리즘을 사용하여 최소 스패닝 트리를 구성합니다. 간선의 조건(최소 거리 이상)을 만족하는 간선만 고려합니다.
• 구현 세부사항:
  • findParent: 경로 압축을 사용하여 부모 노드를 찾습니다.
  • unionParent: 두 점을 하나의 집합으로 합칩니다.
  • 모든 간선의 비용을 계산하고 우선순위 큐에 삽입합니다.
  • 최소 거리 조건(c)을 만족하지 않는 간선은 사용하지 않습니다.
• 시간 복잡도 분석:
  • 간선 계산: O(n²), 여기서 n은 점의 개수
  • 크루스칼 알고리즘: O(E log E), 여기서 E는 간선의 개수
  전체 시간 복잡도는 O(n² + E log E)입니다.

---

결과

주어진 조건을 만족하며 점들을 연결하는 최소 비용을 계산합니다. 모든 점이 연결되지 않을 경우 -1을 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!