[백준 10021 C++] Watering the Fields

Watering the Fields 문제 링크 (BOJ 10021번 문제): https://www.acmicpc.net/problem/10021

10021번: Watering the Fields

문제 설명

BOJ 10021번 Watering the Fields 문제는 특정 C 값보다 큰 간선들로 간선 무게를 최소화하여 모든 노드를 연결하는문제입니다. 

문제 풀이

간선 무게를 최소화하며 모든 노드를 연결하기 하기에 최소 스패닝 트리 알고리즘 (Minimum Spanning Tree) 을 사용하여 문제를 해결할 수 있습니다. 최소 스패닝 트리 알고리즘에서 프림스 알고리즘 (Prim's Algorithm) 과 크루스칼 알고리즘 (Kruskal Algorithm) 중 크루스칼 알고리즘을 사용하였습니다. 

 

크루스칼 알고리즘은 크기가 작은 간선부터 탐색을 진행합니다. 이때, 사이클을 만들지 않기 위해 유니온 파인드 알고리즘을 사용하게 됩니다. 

 

시간복잡도

문제에 들어가기 전에 시간복잡도를 간단하게 구해보고 적용 가능한지 확인해보겠습니다.

 

문제는 N이 최대 2000이며 점과 점을 연결하는 간선(E) 개수는 (N - 1) + (N - 2) + ... + 2 + 1 이므로 E가 넉넉하게 봤을 때 N^2이 되며 크루스칼 알고리즘의 시간복잡도가 O(ElogE) 이므로 2000^2 log (2000^2) 으로 1초 내에 수행될 수 있는 것을 확인할 수 있습니다. 

 

풀이

이 문제에서 주어지는 C 값보다 큰 간선들을 PriorityQueue 에 모두 저장해놓고, PriorityQueue 에서 하나씩 꺼내며 유니온 파인드를 수행하면 해당 문제를 해결할 수 있습니다. 혹은 벡터에 저장한 후 거리가 작은 값을 기준으로 정렬(Sort)를 수행한 후 최소 간선을 이뤄도 됩니다.

 

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

typedef long long ll;
typedef struct point {
    ll distance ; 
    int start, end ; 
} point ; 
typedef pair<ll, ll> pi ; 
struct compare { 
    bool operator() (const point &a, const point &b) { 
        return a.distance > b.distance ; 
    }
};

int N, C ; 
vector<pi> V ; 
int parent[SIZE] ;
priority_queue<point, vector<point>, compare> pq ; 

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

void union_find(int x1, int x2) { 
    x1 = get_parent(x1) ; 
    x2 = get_parent(x2) ; 

    if ( x1 < x2 ) { 
        parent[x2] = x1 ; 
    } else {
        parent[x1] = x2 ; 
    }
}

ll get_distance(int x1, int y1, int x2, int y2) { 
    return (pow((x2 - x1), 2)) + (pow(y2 - y1, 2)) ; 
}

void kruskal() { 
    int cnt = 0 ; 
    ll result = 0 ;
    for (int i = 1; i < N ; i++) { 
        for (int j = i + 1 ; j <= N ; j++) { 
            ll distance = get_distance(V[i].first, V[i].second, V[j].first, V[j].second);
            if ( distance >= C )
                pq.push({distance, i, j});
        }
    }
    
    while ( !pq.empty() ) { 
        ll distance = pq.top().distance ; 
        int start = pq.top().start ; 
        int end = pq.top().end ; 

        pq.pop() ; 
        start = get_parent(start) ; 
        end = get_parent(end) ; 

        if ( start != end ) { 
            union_find(start, end) ; 
            result += distance ; 
            cnt++ ; 
            if (cnt == N - 1) { 
                break; 
            }
        }
    }

    if ( cnt != N - 1 ) cout << -1 << '\n'; 
    else cout << result << '\n'; 
}

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

    cin >> N >> C ; 
    V.push_back({0,0}); // Not used
    for (int i = 1 ; i <= N ; i++) { 
        int x1,y1; cin >> x1 >> y1 ; 
        V.push_back({x1, y1}) ; 
        parent[i] = i ; 
    } 

    kruskal() ; 
    
    return 0 ;
}