[C++]백준 17197번 Fence Planning

📌문제 링크

---

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

📌문제 설명

---

각 집합의 ((x최댓값 - x최솟값) + (y최댓값 - y최솟값)) * 2중 가장 작은 값을 출력하면 됩니다. 분리집합으로도 가능하고 dfs로도 풀이 가능합니다.

📌코드

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>
using namespace std;
vector<pair<int,int>> cord, link;
int N, M, parent[100001];

void input(){
    cin >> N >> M;
    cord.resize(N);
    for(auto &it : cord){
        cin >> it.first >> it.second;
    }
    link.resize(M);
    for(auto &it : link){
        cin >> it.first >> it.second;
    }
}

void init(){
    for(int i = 0; i <= N; i++){
        parent[i] = i;
    }
}

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

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

void solve(){
    input();
    init();
    for(auto it : link){
        unite(it.first - 1, it.second - 1);
    }
    vector<int> x_min(N, INT_MAX), x_max(N, INT_MIN);
    vector<int> y_min(N, INT_MAX), y_max(N, INT_MIN);
    for(int i = 0; i < N; i++){
        int root = findParent(i);
        x_min[root] = min(x_min[root], cord[i].first);
        x_max[root] = max(x_max[root], cord[i].first);
        y_min[root] = min(y_min[root], cord[i].second);
        y_max[root] = max(y_max[root], cord[i].second);
    }
    int ans = INT_MAX;
    for(int i = 0; i < N; i++){
        if(x_min[i] == INT_MAX){
            continue;
        }
        ans = min(ans, 2 * (x_max[i] - x_min[i] + y_max[i] - y_min[i]));
    }
    cout << ans;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}