[백준] 1774번 : 우주신과의 교감

문제

 

---

풀이

 

myunji.tistory.com/370

이 문제에서 각 정점이 좌표로 표현되는 정도만 달라졌다고 생각할 수도 있지만...하나 더 생각할 것이 있다.

바로 이미 연결된 정점들이 주어진다는 것이다.

 

처음엔 초기 연결 정점들이 다 연결가능하겠거니 하고 코드를 작성했다가 아닐 수도 있단 것을 깨달았다.

그니까 간단하게 예를 들자면

4 2
1 1
3 1
2 3
4 3
1 4
4 1

이렇게 입력이 들어와서 이미 1-4를 연결했는데 4-1을 연결하려고 할 수도 있다는 뜻이다.

이 부분만 신경쓰면 크게 어려울건 없다.

---

소스코드

 

 

#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <cmath>

using namespace std;
typedef pair<int, int> pp;

int v_cnt; //사용한 간선의 수
vector<pair<double, double>> pos; //각 별의 x, y 좌표
priority_queue<pair<double, pp>, vector<pair<double, pp>>, greater<pair<double, pp>>> pq; //min-heap
vector<int> parent;

int findParent(int x) { //parent[x]가 음수가 될 때까지(root에 다다를 때까지) 재귀 함수 호출
    if (parent[x] < 0)
        return x;
    return parent[x] = findParent(parent[x]);
}

bool unionInput(int x, int y) {
    int x_p = findParent(x); //x의 부모
    int y_p = findParent(y); //y의 부모

    if (x_p == y_p) //이미 같은 집합, 이 간선 쓸 수 없음
        return false;
    if (parent[x_p] < parent[y_p]) { //x_p를 root로 하는 노드가 더 많으면 x_p -> y_p
        parent[x_p] += parent[y_p];
        parent[y_p] = x_p;
    } else { //y_p를 root로 하는 노드가 더 많으면 y_p -> x_p
        parent[y_p] += parent[x_p];
        parent[x_p] = y_p;
    }
    return true;
}

double kruskalMst(int V) {
    double weight = 0;

    while (v_cnt != (V - 1)) { //사용한 간선이 V-1개이면 break
        double dist = pq.top().first; //간선의 weight
        int x = pq.top().second.first;
        int y = pq.top().second.second;

        pq.pop();
        if (unionInput(x, y)) { //x, y를 유니온할 수 있다면
            v_cnt++;
            weight += dist;
        }
    }
    return weight; //그래프의 가중치 합
}

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

    int n, m, x, y;
    double a, b;

    cin >> n >> m;
    parent.assign(n + 1, -1);
    pos.push_back(make_pair(-1, -1));
    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        pos.push_back(make_pair(a, b));
    }
    for (int i = 1; i <= n - 1; i++) { //모든 입력들 사이의 거리를 구해서 min-heap에 투입
        for (int j = i + 1; j <= n; j++) {
            double distance = pow((pos[i].first - pos[j].first), 2) + pow((pos[i].second - pos[j].second), 2);
            pq.push(make_pair(sqrt(distance), make_pair(i, j)));
        }
    }
    for (int i = 0; i < m; i++) {
        cin >> x >> y;
        if (unionInput(x, y)) //유니온 했다면 v_cnt 증가
            v_cnt++;
    }
    cout << fixed;
    cout.precision(2);
    cout << kruskalMst(n);
}

전체 소스코드다.

 

int v_cnt; //사용한 간선의 수
vector<pair<double, double>> pos; //각 입력의 x, y 좌표
priority_queue<pair<double, pp>, vector<pair<double, pp>>, greater<pair<double, pp>>> pq; //min-heap
vector<int> parent;

지금까지 트리에 사용된 간선의 수를 전역변수로 관리할 것이다.

그리고 각 입력의 x, y 좌표를 저장할 벡터도 선언한다.

kruskal로 MST를 만들 것이니 min-heap과 parent 벡터도 필요하다.

 

    for (int i = 1; i <= n - 1; i++) { //모든 입력들 사이의 거리를 구해서 min-heap에 투입
        for (int j = i + 1; j <= n; j++) {
            double distance = pow((pos[i].first - pos[j].first), 2) + pow((pos[i].second - pos[j].second), 2);
            pq.push(make_pair(sqrt(distance), make_pair(i, j)));
        }
    }

모든 입력이 1000개 이하기 때문에 맘 편하게 모든 입력들 사이의 거리를 구해 min-heap에 넣는다.

설마 두 좌표 사이의 거리를 구하는 공식을 잊고 이 글을 보진 않으리라 생각한다.

 

    for (int i = 0; i < m; i++) {
        cin >> x >> y;
        if (unionInput(x, y)) //유니온 했다면 v_cnt 증가
            v_cnt++;
    }

그리고 m개의 x, y에 대해 먼저 유니온을 해둔다. 유니온에 성공했다면 v_cnt를 증가해준다.

 

유니온 파인드 함수에 대한건

myunji.tistory.com/367

[백준] 1717번 : 집합의 표현

여기 있다.

 

    cout << fixed;
    cout.precision(2);
    cout << kruskalMst(n);

그리고 소수점 고정하고 kruskalMst 함수를 호출하면 된다.

 

double kruskalMst(int V) {
    double weight = 0;

    while (v_cnt != (V - 1)) { //사용한 간선이 V-1개이면 break
        double dist = pq.top().first; //간선의 weight
        int x = pq.top().second.first;
        int y = pq.top().second.second;

        pq.pop();
        if (unionInput(x, y)) { //x, y를 유니온할 수 있다면
            v_cnt++;
            weight += dist;
        }
    }
    return weight; //그래프의 가중치 합
}

이 코드는

 

myunji.tistory.com/370

여기 있는 코드와 같다.