백준 2887번 행성 터널

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

교내 알고리즘 대회 문제 행성 연결(http://jaimemin.tistory.com/980)와 똑같은 문제였습니다.

다만, 행성 연결 문제는 2차원이였기 때문에 해당 문제가 난이도가 더 있는 것 같습니다.

알고리즘은 아래와 같습니다.

1. 행성의 좌표가 입력되므로 해당 좌표에 대해 인덱스를 부여합니다.

2. min({(a.x - b.x), (a.y, b.y), (a.z, b.z)})가 간선의 가중치이므로 x를 기준으로, y를 기준으로, z를 기준으로 각각 정렬한 뒤 간선 벡터에 전부 넣어줍니다.

3. 2번을 진행한 뒤 오름차순 정렬을 하여 크루스칼 알고리즘을 적용하면 답이 나옵니다.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

const int MAX = 100000;

 

int parent[MAX], setSize[MAX];

 

//루트 찾는 함수

int findParent(int node)

{

        //현재 노드가 집합의 루트라면

        //자신이 속한 집합을 찾았으므로 node 반환

        if (node == parent[node])

                 return node;

 

        //현재 노드가 집합의 루트가 아니라면

        //노드의 루트에 대해 재귀 호출하면서 parent[node] 업데이트

        return parent[node] = findParent(parent[node]);

}

 

//집합을 합치는 함수

void merge(int node1, int node2)

{

        node1 = findParent(node1); //node1이 속한 집합을 찾음

        node2 = findParent(node2); //node2가 속한 집합을 찾음

                                                             //같은 집합이 아닐 경우에만 합친다

        if (node1 != node2)

        {

                 //크기가 더 큰 집합으로 작은 집합이 들어감

                 if (setSize[node1] < setSize[node2])

                         swap(node1, node2);

 

                 parent[node2] = node1; //node2 집합이 node1에 합쳐짐

                 setSize[node1] += setSize[node2]; //node1의 집합 크기가 커짐

                 setSize[node2] = 0; //node2가 node1에 흡수되므로

        }

}

 

//간선을 표현하는 구조체

struct Edge {

        int u, v, weight; //u, v는 정점

                                            //weight는 가중치

 

         //정렬을 위해 오버로딩

        bool operator<(Edge const &e)

        {

                 return weight < e.weight;

        }

};

 

struct planet

{

        int idx, x, y, z; //인덱스, x, y, z

        int distance(const planet &p)

        {

                 return min({ abs(x - p.x), abs(y - p.y), abs(z - p.z) });

        }

};

 

bool cmpX(planet &a, planet &b)

{

        if (a.x < b.x)

                 return true;

        return false;

}

 

bool cmpY(planet &a, planet &b)

{

        if (a.y < b.y)

                 return true;

        return false;

}

 

bool cmpZ(planet &a, planet &b)

{

        if (a.z < b.z)

                 return true;

        return false;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N;

        cin >> N;

 

        vector<planet> p(N);

        //초기화

        for (int i = 0; i < N; i++)

        {

                 parent[i] = i;

                 setSize[i] = 1;

        }

        for (int i = 0; i < N; i++)

        {

                 cin >> p[i].x >> p[i].y >> p[i].z;

                 p[i].idx = i;

        }

 

        vector<Edge> edge;

        //x, y, z를 기준으로 오름차순한 간선을 다 Edge에 넣어준다

        sort(p.begin(), p.end(), cmpX);

        for (int i = 1; i < N; i++)

                 edge.push_back({ p[i - 1].idx, p[i].idx, p[i - 1].distance(p[i]) });

        sort(p.begin(), p.end(), cmpY);

        for (int i = 1; i < N; i++)

                 edge.push_back({ p[i - 1].idx, p[i].idx, p[i - 1].distance(p[i]) });

        sort(p.begin(), p.end(), cmpZ);

        for (int i = 1; i < N; i++)

                 edge.push_back({ p[i - 1].idx, p[i].idx, p[i - 1].distance(p[i]) });

        //간선의 가중치를 기준으로 오름차순 정렬

        sort(edge.begin(), edge.end());

        long long result = 0;

        for (int i = 0; i < edge.size(); i++)

        {

                 Edge e = edge[i];

                 //같은 집합이 아닐 때만 추가

                 if (findParent(e.u) != findParent(e.v))

                 {

                         result += e.weight;

                         merge(e.u, e.v);

                 }

        }

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~