[BOJ] 백준 2887 행성 터널 / 최소 신장 트리(MST), 크루스칼

이미지를 클릭하면 문제 사이트로 이동합니다.

---

 

 

💣 문제 이해

 

x, y, z 좌표로 행성의 위치가 주어지고(노드), 그 행성들 사이의 거리가 가중치가 된다(간선).

행성과 행성 사이의 거리는 문제에 주어진 조건처럼 min(abs(x1-x2), abs(y1-y2), abs(z1-z2))가 된다.

 

이 문제는 크루스칼 알고리즘으로 풀이했다.

 

 

💭 풀이 과정

 

 

작성 언어: C++

 

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

class Planet {
public:
    int x, y, z, index;
    Planet(int x, int y, int z, int index) {
        this->x = x;
        this->y = y;
        this->z = z;
        this->index = index;
    }
};

class Tunnel {
public:
    int start, dest, cost;
    Tunnel(int start, int dest, int cost) {
        this->start = start;
        this->dest = dest;
        this->cost = cost;
    }
};

int planet_cnt = 0;
int result = 0;
const int MAX = 100001;
vector<Planet>planets;
vector<Tunnel>tunnels;
int parent[MAX] = {0, };

bool compare_x(const Planet &p1, const Planet &p2) {
    return p1.x < p2.x;
}

bool compare_y(const Planet &p1, const Planet &p2) {
    return p1.y < p2.y;
}

bool compare_z(const Planet &p1, const Planet &p2) {
    return p1.z < p2.z;
}

bool compare_cst(const Tunnel &t1, const Tunnel &t2) {
    return t1.cost < t2.cost;
}

int getCost(const Planet p1, const Planet p2) {
    int x_dist = abs(p1.x - p2.x);
    int y_dist = abs(p1.y - p2.y);
    int z_dist = abs(p1.z - p2.z);
    return min(x_dist, min(y_dist, z_dist));
}

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

void mergeTree(int node1, int node2) {
    int node1_p = getParent(node1);
    int node2_p = getParent(node2);
    
    parent[node1_p] = node2_p;
}


int main() {
    cin >> planet_cnt;
    for (int i = 0; i < planet_cnt; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        planets.push_back(Planet(x, y, z, i));
    }
    
    for (int i = 0; i < planet_cnt; ++i) {
        parent[i] = i;
    }
    
    sort(planets.begin(), planets.end(), compare_x);
    for (int i = 0; i < planet_cnt-1; ++i)
        tunnels.push_back(Tunnel(planets[i].index, planets[i+1].index, getCost(planets[i], planets[i+1])));
    sort(planets.begin(), planets.end(), compare_y);
    for (int i = 0; i < planet_cnt-1; ++i)
        tunnels.push_back(Tunnel(planets[i].index, planets[i+1].index, getCost(planets[i], planets[i+1])));
    sort(planets.begin(), planets.end(), compare_z);
    for (int i = 0; i < planet_cnt-1; ++i)
        tunnels.push_back(Tunnel(planets[i].index, planets[i+1].index, getCost(planets[i], planets[i+1])));
    
    sort(tunnels.begin(), tunnels.end(), compare_cst);
    for (int i = 0; i < tunnels.size(); ++i) {
        if (getParent(tunnels[i].start) != getParent(tunnels[i].dest)) {
            result += tunnels[i].cost;
            mergeTree(tunnels[i].start, tunnels[i].dest);
        }
    }
    
    cout << result << endl;
    
    return 0;
}

 

일반적인 최소 신장 트리 문제와 비슷하지만, 행성과 행성을 연결하는 모든 경로를 저장하면 메모리 초과가 발생한다.

따라서 x축, y축, z 축으로 바로 인접한 행성들끼리의 경로만 저장하면 문제없이 해결할 수 있다.