백준 2887 - 행성 터널(C++)

문제 링크입니다 https://www.acmicpc.net/problem/2887

2887번: 행성 터널

2차원 공간에서의 최소 비용 구하기와 다르게 3차원이면서 N의 범위도 100,000 까지이기에 까다로운 문제였습니다. 방법을 생각하는데 꽤 오래걸린 것 같습니다.(괜히 골드1 문제가 아니였습니다)

 

문제 조건

출력 예시

 

문제 접근 방법

 

1. 각 좌표들을 입력받는다.(저는 구조체로 입력받았습니다)

2. 좌표들을 X, Y, Z축에 따라 오름차순으로 정렬한다.

3. 각 축으로 정렬하면서 자신과 i와 i+1번째 행성들의 X, Y, Z 좌표의 최소 차이값을 구한 다음, 행성을 연결시키는 선으로 만들어준다.(X, Y, Z축 3번을 해주면 됩니다)

4. 선을 전부 저장했으면, 비용에 따라 오름차순으로 정렬해준다.

5. Union() + Find() 함수를 통해서 쿠르스칼 알고리즘을 만들어, MST를 해준다.

 

 

문제 접근 방법 - 2번, 3번

bool cmp_x(si a, si b) {
    if (a.x < b.x) return true;
    return false;
}
void get_x() {
    sort(site.begin(), site.end(), cmp_x);
    for (int i = 0; i < site.size()-1; i++) {
        long long int mini = min(min(abs(site[i].x - site[i + 1].x), abs(site[i].y - site[i + 1].y)), abs(site[i].z - site[i + 1].z));
        planet.push_back({site[i].num, site[i+1].num, mini});
    }
}

X, Y, Z 축 중에서 X축 코드만 가져왔습니다. Y, Z축은 X축과 거의 똑같습니다.

먼저 X축의 좌표에 따라 오름차순을 했습니다. 그 다음에는 i번과 i+1번의 좌표를 비교했습니다. 거리는 양수기에서 abs를 통해서 절댓값을 해줬습니다. X, Y, Z 축 차이중에서 가장 작은 값을 행성간의 선을 저장하는 백터에 저장했습니다.

 

 

문제 접근 방법 - 5번

int Find(int x) {
    if (connect[x] == x) return x;
    else return connect[x] = Find(connect[x]);
}
void Union(int x, int y) {
    int xx = Find(x);
    int yy = Find(y);
    connect[xx] = yy;
}
for (int i = 0; i < planet.size(); i++) {
        int x = Find(planet[i].start);
        int y = Find(planet[i].finish);
        if (x != y) {
            Union(x, y);
            mini_cost += planet[i].cost;
        }
 }

쿠르스칼 알고리즘 부분만 가져왔습니다.

planet 백터에는 행성간의 연결 간선의 정보들이 들어있습니다. for문을 통해서 처음부터 끝까지 선들의 출발 지점과 도착 지점의 값을 받아서 Find() 함수에 넣어줍니다.

Find() 함수에선 각 행성이 어디까지 연결되어 있는지를 찾아줍니다.

만약 출발 지점과 도착 지점이 연결되어 있는 마지막 행성의 번호가 같다면 이어줄 필요가 없습니다. 다르다면 이들은 연결이 되어 있지 않은 상태이기에 Union() 함수를 통해서 이들을 연결시켜 준다음, 비용을 더해줍니다. 

 

 

자세한 것은 코드를 참고해주세요!

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
using namespace std;

int num_planet;
typedef struct si {
    int num;
    int x;
    int y;
    int z;
}si;
typedef struct li {
    int start;
    int finish;
    long long int cost;
}li;
vector<si> site;
vector<li> planet;
int connect[100011];


bool cmp_x(si a, si b) {
    if (a.x < b.x) return true;
    return false;
}
bool cmp_y(si a, si b) {
    if (a.y < b.y) return true;
    return false;
}
bool cmp_z(si a, si b) {
    if (a.z < b.z) return true;
    return false;
}

void get_x() {
    sort(site.begin(), site.end(), cmp_x);
    for (int i = 0; i < site.size()-1; i++) {
        long long int mini = min(min(abs(site[i].x - site[i + 1].x), abs(site[i].y - site[i + 1].y)), abs(site[i].z - site[i + 1].z));
        planet.push_back({site[i].num, site[i+1].num, mini});
    }
}
void get_y() {
    sort(site.begin(), site.end(), cmp_y);
    for (int i = 0; i < site.size() - 1; i++) {
        long long int mini = min(min(abs(site[i].x - site[i + 1].x), abs(site[i].y - site[i + 1].y)), abs(site[i].z - site[i + 1].z));
        planet.push_back({ site[i].num, site[i + 1].num, mini });
    }
}
void get_z() {
    sort(site.begin(), site.end(), cmp_z);
    for (int i = 0; i < site.size() - 1; i++) {
        long long int mini = min(min(abs(site[i].x - site[i + 1].x), abs(site[i].y - site[i + 1].y)), abs(site[i].z - site[i + 1].z));
        planet.push_back({ site[i].num, site[i + 1].num, mini });
    }
}

bool cmp(li a, li b) {
    if (a.cost < b.cost) return true;
    return false;
}

int Find(int x) {
    if (connect[x] == x) return x;
    else return connect[x] = Find(connect[x]);
}

void Union(int x, int y) {
    int xx = Find(x);
    int yy = Find(y);
    connect[xx] = yy;
}

void solve() {
    long long int mini_cost = 0;
    get_x();
    get_y();
    get_z();
    sort(planet.begin(), planet.end(), cmp);
    for (int i = 0; i <= num_planet; i++) {
        connect[i] = i;
    }
    for (int i = 0; i < planet.size(); i++) {
        int x = Find(planet[i].start);
        int y = Find(planet[i].finish);
        if (x != y) {
            Union(x, y);
            mini_cost += planet[i].cost;
        }
    }
    cout << mini_cost;
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin >> num_planet;
    for (int i = 0; i < num_planet; i++) {
        int xx, yy, zz;
        cin >> xx >> yy >> zz;
        site.push_back({i+1,xx,yy,zz });
    }
    solve();
    return 0;
}

 

질문 및 조언 댓글 남겨주세요!