백준 2887번 행성 터널

 

문제

때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.

행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다.

민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다. 

출력

첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다.

 

 

 

처음에는 1+....+N-1 의 횟수로 vec에 모든 연결관계를 다 넣어줘서 sort시킨후 위에서부터 정렬 했는데 , 메모리초과가 발생하였다.  그런데 생각해보면 굳이 모든 연결관계를 알아야 할 필요가 있을까? 예를 들어 인덱스 1 기준으로 다른 정점까지의 거리중 필요한 정보는 최소의 cost값을 가진 경로 뿐이다. 그니까 즉 1을 기준으로 해서 x좌표 값의 크기로 정렬 했을 때 1과 인접해 있는 두 정점 , 그리고 y좌표 z좌표로 각각 정렬했을 때 인접해있는 정점들이 1을 기준으로 했을때 1에서 연결되어 최소값을 낼 수 있는 정점들이고 그 나머지 정점들은 최소 스패닝 트리에서 의미가 없다. 따라서 그 cost로 연결된 경로들이 저장되고 나머지 정점들에 대해서도 마찬가지이다 . 그 후에 전체적으로 vec을 cost기준으로 오름차순 정렬시키면  1에서 이동할 수 있는 경로중 최소의 값이 가장 위에 올라오게 되고 이때 그정점과 연결이 되어버리면 그 정점과 1과 관련된 다른 연결관계는 자동으로 findparent함수를 통해 걸러지므로 연결이 무시된다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int parent[100000];



int findparent(int node)
{

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

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

}

void merge(int pos1, int pos2)
{
   int node1 = findparent(pos1);
   int node2 = findparent(pos2);
   
   if(node1 != node2)
   {
   
     parent[node1] = node2;


}
   
   
   
   
   
   
   


}


int mini(int a, int b, int c)
{

if(a<=b && a<=c)
{
return a;
}

else if(b<=a && b<=c)
{
return b;
}

else if(c<=a && c<=b)
{
return c;
}

}

struct Edge{

int a;
int b;
int cost;


bool operator<(Edge &e)
{
return cost < e.cost;
     }
};

struct Node{

int index;

int x;
int y;
int z;



};


bool cmpx(Node &a , Node &b)
{
if(a.x < b.x)
return true;

return false;

}
bool cmpy(Node &a , Node &b)
{
if(a.y < b.y)
return true;

return false;

}
bool cmpz(Node &a , Node &b)
{
if(a.z < b.z)
return true;

return false;

}

vector vec;



int main(void)
{



int N;
int result = 0;

cin >> N;
vector node(N);

for(int i=0; i<N; i++)
{
cin >> node[i].x >> node[i].y >> node[i].z;

node[i].index = i;

parent[i] = i;



}

sort(node.begin(), node.end(),cmpx);
for(int i=0; i<N-1; i++)
{
vec.push_back({node[i].index, node[i+1].index, mini(abs(node[i].x-node[i+1].x),abs(node[i].y-node[i+1].y),abs(node[i].z-node[i+1].z))});
}
sort(node.begin(), node.end(),cmpy);
for(int i=0; i<N-1; i++)
{
vec.push_back({node[i].index, node[i+1].index, mini(abs(node[i].x-node[i+1].x),abs(node[i].y-node[i+1].y),abs(node[i].z-node[i+1].z))});
}
sort(node.begin(), node.end(),cmpz);
for(int i=0; i<N-1; i++)
{
vec.push_back({node[i].index, node[i+1].index, mini(abs(node[i].x-node[i+1].x),abs(node[i].y-node[i+1].y),abs(node[i].z-node[i+1].z))});
}


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






for(int i =0 ; i<vec.size(); i++)
{
int pos1 = vec[i].a;
int pos2 = vec[i].b;

  if(findparent(pos1)!=findparent(pos2))
{
merge(pos1,pos2);
result += vec[i].cost;

     }


}


cout << result;



}