Baekjoon 10021번 Watering the Fields

문제

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

걸린 시간

- 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

struct DisjointSet{
    vector<int> parent, rank;
    DisjointSet(int n): parent(n), rank(n, 1){
        for(int i = 0; i < n; i++)
            parent[i] = i;
    }
    int find(int u) {
        if(u == parent[u]) return u;
        return parent[u] = find(parent[u]);
    }
    void merge(int u, int v){
        u = find(u); v = find(v);
        if(u == v) return;
        if(rank[u] > rank[v]) swap(u, v);
        parent[u] = v;
        if(rank[u] == rank[v]) rank[v]++;
    }
};

struct node{
    int u, v, cost;
    node(int u, int v, int cost){
        this->u = u;
        this->v = v;
        this->cost = cost;
    }
};

bool compare(node a, node b){
    return a.cost < b.cost;
}

int n, c;
int x[2000], y[2000];
int adj[2000][2000];

int kruskal(){
    int ret = 0, cnt = 0;
    vector<node> edges;
    for(int u = 0; u < n; u++)
        for(int v = 0; v < n; v++)
            if(adj[u][v] != 0)
                edges.push_back(node(u, v, adj[u][v]));
    sort(edges.begin(), edges.end(), compare);
    DisjointSet sets(n);
    for(int i = 0; i < edges.size(); i++){
        int cost = edges[i].cost;
        int u = edges[i].u;
        int v = edges[i].v;
        if(sets.find(u) == sets.find(v)) continue;
        sets.merge(u, v);
        ret += cost;
        cnt++;
    }
    if(cnt == n-1) return ret;
    else return -1;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> c;
    for(int i = 0; i < n; i++)
        cin >> x[i] >> y[i];
    memset(adj, 0, sizeof(adj));
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++){
            int dist = pow(x[i]-x[j], 2)+pow(y[i]-y[j], 2);
            if(dist >= c) adj[i][j] = dist;
        }
    cout << kruskal();
    return 0;
}

최소 스패닝 트리 개념을 모르고 prefix sum 으로 접근했다. 사이클 없이 n개의 field 가 n-1개의 간선으로 연결되도록 하였지만 작은 예제 만으로도 쉽게 반례를 찾을 수 있었다. 인접한 좌표의 개수와 가중치들의 합을 기준으로 정렬도 해 보았지만 한계가 존재했고, 결국 kruskal 알고리즘을 공부하여 해결했다.