백준 - 행성터널(2887)

그냥 MST문제인가 생각하고

크루스칼 알고리즘을 적용해 보았다.

 

 

아래 코드는 실패한 코드이다.

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>
using namespace std;   


vector<int> table;

int find(int root)
{
    if (table[root] != root) {
        table[root] = find(table[root]);
    }
    return table[root];
}

int find_union(int a, int b)
{
    int root_a = find(a);
    int root_b = find(b);

    if (root_a < root_b) {
        table[root_b] = root_a;
    }
    else{
        table[root_a] = root_b;
    }
    
    if (root_a == root_b) return 0;
    return 1;
}


int main()
{
    int n;
    cin >> n;
    vector<vector<int>> route(n, { 0, 0, 0 });
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
    for (int i = 0; i < n; i++) table.push_back(i);
    for (int i = 0; i < n; i++) cin >> route[i][0] >> route[i][1] >> route[i][2];
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++)
        {
            int min_data = min({ abs(route[i][0] - route[j][0]), abs(route[i][1] - route[j][1]), abs(route[i][2] - route[j][2]) });
            pq.push(tuple<int, int, int>(min_data, i, j));
        }
    }



    //cout << pq.size() << endl;
    int answer = 0;
    while (pq.size())
    {       
        if (find_union(get<1>(pq.top()), get<2>(pq.top()))) {           
            //cout << get<0>(pq.top()) << " " << get<1>(pq.top()) << " " << get<2>(pq.top()) << endl;
            answer += get<0>(pq.top());
        }
        
        pq.pop();     
    }
    cout << answer << endl;
}

간선을 전부 구하고 union find를 통해

최상단 노드를 비교해서 같지 않을 경우는 전부 answer에 더했다.

답은 맞게 나오나 메모리 용량이 초과했다.

 

 

그래서 다음 방법은

X, Y, Z를 자기들끼리 정렬한다.

정렬할 때는 자기의 행성 번호도 값이 들어간다.

 

 

X : -1  10  11  14  19

Y : -15  -5  -4  -4  -1

Z : -15  -15  -5  -1  19

 

 

인덱스 순서를 i라 하면 [i + 1] - [i]를 해주고 벡터에 빼준값과 행성 번호 두 개의 값을 넣어준다.

 

 for (int i = 0; i < n; i++) {
     int x, y, z;
     cin >> x >> y >> z;
     x_data.push_back({ x, i });
     y_data.push_back({ y, i });
     z_data.push_back({ z, i });
     table.push_back(i);
 }
 sort(x_data.begin(), x_data.end());
 sort(y_data.begin(), y_data.end());
 sort(z_data.begin(), z_data.end());

 for (int i = 0; i < n - 1; i++) {
     planet.push_back({ abs(x_data[i + 1].first - x_data[i].first), x_data[i + 1].second, x_data[i].second });
     planet.push_back({ abs(y_data[i + 1].first - y_data[i].first), y_data[i + 1].second, y_data[i].second });
     planet.push_back({ abs(z_data[i + 1].first - z_data[i].first), z_data[i + 1].second, z_data[i].second });
 }

 sort(planet.begin(), planet.end());
 for (int i = 0; i < planet.size(); i++) {
     cout << get<0>(planet[i]) << " " << get<1>(planet[i]) << " " << get<2>(planet[i]) << endl;
 }

 

마지막 데이터가 전부 들어간 벡터를 정렬해 준다.

 

최종적으로 planet 벡터에는

거리, 행성 A, 행성 B

0 1 0
0 4 3
1 0 3
1 3 1
3 1 0
3 2 4
4 3 2
5 4 1
10 1 0
10 2 1
11 3 2
20 4 3

 

이런 데이터가 들어가 있다.

이 상태로 크루스칼 알고리즘을 적용한다.

 

 

 

 

 

전체 코드

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>
using namespace std;


vector<int> table;

int find(int root)
{
    if (table[root] != root) {
        table[root] = find(table[root]);
    }
    return table[root];
}

int find_union(int a, int b)
{
    int root_a = find(a);
    int root_b = find(b);

    if (root_a < root_b) {
        table[root_b] = root_a;
    }
    else {
        table[root_a] = root_b;
    }

    if (root_a == root_b) return 0;
    return 1;
}


int main()
{
    int n;
    cin >> n;
    vector<tuple<int, int, int>> planet;
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
    vector<pair<int, int>> x_data;
    vector<pair<int, int>> y_data;
    vector<pair<int, int>> z_data;

    for (int i = 0; i < n; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        x_data.push_back({ x, i });
        y_data.push_back({ y, i });
        z_data.push_back({ z, i });
        table.push_back(i);
    }
    sort(x_data.begin(), x_data.end());
    sort(y_data.begin(), y_data.end());
    sort(z_data.begin(), z_data.end());

    for (int i = 0; i < n - 1; i++) {
        planet.push_back({ abs(x_data[i + 1].first - x_data[i].first), x_data[i + 1].second, x_data[i].second });
        planet.push_back({ abs(y_data[i + 1].first - y_data[i].first), y_data[i + 1].second, y_data[i].second });
        planet.push_back({ abs(z_data[i + 1].first - z_data[i].first), z_data[i + 1].second, z_data[i].second });
    }

    sort(planet.begin(), planet.end());
    //for (int i = 0; i < planet.size(); i++) {
    //    cout << get<0>(planet[i]) << " " << get<1>(planet[i]) << " " << get<2>(planet[i]) << endl;
    //}


    int answer = 0;
    for (int i = 0; i < planet.size(); i++)
    {
        if (find_union(get<1>(planet[i]), get<2>(planet[i])))
        {
            answer += get<0>(planet[i]);
        }
    }
    
    cout << answer << endl;
}