백준 14401번: 악덕 나라 (C++)

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

14401번: 악덕 나라

---

Solved By: Kruskal, CCW

 

좌표값이 존재하여 좌표 간의 거리를 구한 후, 최댓값을 구하기 때문에 Edge의 비용을 음수 값으로 바꾸어주고, 이미 있는 고속도로라면 두 노드를 union 하여 거리를 구한 Edge들을 Kruskal 돌리면 되는 간단한 문제일 줄 알았습니다.

 

하지만, 문제에서 "고속도로 하나하나는 다른 도시들을 거치지 않아야 하며"라는 조건이 있기 때문에 이를 신경 써줘야 합니다.

 

이를 해결하기 위해 3중 for문을 사용할 것인데 n의 MAX 값이 500이라 충분해 보입니다.

1. j를 i와 k 사이의 점이라 보고 i, j의 거리와 j, k의 거리가 같음을 보아 j는 i와 k 사이의 중간점임을 확인하고

2. i, j, k의 CCW 값이 0이라면 세 점은 한 직선상에 있는 것을 확인합니다.

 

즉, j는 i와 k 사이에 있으며 i와 k에 고속도로를 지었을 때 j를 거치므로 i, k 사이에는 고속도로를 짓지 말아야 합니다.

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
#define MAX 501
#define pii pair<int, int>
using namespace std;

int N, M;
struct Point{
    ll x, y;
};
vector<Point> v;
int parent[MAX];
vector<pair<pii, ll>> edges;

ll getCost(Point a, Point b){
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

ll ccw(Point a, Point b, Point c){
    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

bool cmp(pair<pii, ll> a, pair<pii, ll> b){
    return a.second < b.second;
}

int getRoot(int node){
    if(node == parent[node]) return node;
    else return parent[node] = getRoot(parent[node]);
}

bool find(int a, int b){
    int ga = getRoot(a);
    int gb = getRoot(b);
    
    if(ga != gb) return true;
    else return false;
}

void unionNodes(int a, int b){
    int ga = getRoot(a);
    int gb = getRoot(b);
    
    if(ga < gb) parent[gb] = ga;
    else parent[ga] = gb;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> N >> M;
    
    // init
    for(int i = 1; i <= N; i++) parent[i] = i;
    v.push_back({0, 0});
    
    for(int i = 1; i <= N; i++){
        ll x, y; cin >> x >> y;
        v.push_back({x, y});
    }
    
    bool over_city[MAX][MAX];
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){ // j를 중간점으로 취급
            for(int k = 1; k <= N; k++){
                if(i == j || j == k || i == k) continue;
                
                if(getCost(v[i], v[j]) == getCost(v[j], v[k])){
                    if(ccw(v[i], v[j], v[k]) == 0){
                        over_city[i][k] = true;
                    }
                }
            }
        }
    }
    
    for(int i = 1; i <= N; i++){
        for(int j = i + 1; j <= N; j++){
            if(over_city[i][j]) continue;
            edges.push_back({{i, j}, -getCost(v[i], v[j])}); // 최대 MST
        }
    }
    
    sort(edges.begin(), edges.end(), cmp);
    
    for(int i = 0; i < M; i++){
        int a, b; cin >> a >> b;
        unionNodes(a, b);
    }
    
    ll res = 0;
    for(int i = 0; i < edges.size(); i++){
        int first = edges[i].first.first;
        int second = edges[i].first.second;
        //cout << first << ' ' << second << '\n';
        //cout << -edges[i].second << '\n';
        if(find(first, second)){
            unionNodes(first, second);
            res -= edges[i].second;
        }
    }
    
    cout << res; 
    return 0;
}