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

문제 출처 : https://www.acmicpc.net/problem/2887

 

<접근 방법>

1. 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구해야 함 -> MST (Kruscal Algorithm 이용)

2. Kruscal을 이용하려면 간선이 필요 -> min(|Xa-Xb|, |Ya-Yb|, |Za-Zb|)로 설정

But 행성의 갯수가 최대 10만개이기 때문에 모든 간선을 구현하면 메모리 초과 발생 메모리 초과 아니더라도 시간초과 될 수도 있음

3. 우리가 필요한 간선은 비용이 최소인 간선이기 때문에 각 x,y,z에 대하여 가장 가까운 즉 최소 비용을 가지는 간선들만 찾아서 벡터에 푸쉬쉬유니온 파인드를 하여 최소 스패닝 트리 찾기

 

<풀이>

1. 각 행성의 번호, x, y, z값을 모두 넣기 위해 Pos구조체 생성

2. 벡터 생성 후 input값 받아오기

3. x,y,x 각각에 대하여 정렬 후 push

4. Kruscal Algorithm 이용

 

<소스 코드>

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#define MAX 100000
 
using namespace std;
 
struct Pos{
  int num,x,y,z;
};
 
int N, Parent[MAX], result=0;
vector<Pos> p_vec;
vector<pair<int,pair<int,int>>> Vec;
 
bool comp1(Pos &a, Pos &b){
  if(a.x<b.x) return true;
  return false;
}
bool comp2(Pos &a, Pos &b){
  if(a.y<b.y) return true;
  return false;
}
bool comp3(Pos &a, Pos &b){
  if(a.z<b.z) return true;
  return false;
}
 
void Sort(){
  sort(p_vec.begin(),p_vec.end(),comp1);
  for(int i=0; i<N-1; i++){
    int val = min(abs(p_vec[i].x-p_vec[i+1].x),abs(p_vec[i+1].x-p_vec[i].x));
    Vec.push_back({val,{p_vec[i].num,p_vec[i+1].num}});
  }
  sort(p_vec.begin(),p_vec.end(),comp2);
  for(int i=0; i<N-1; i++){
    int val = min(abs(p_vec[i].y-p_vec[i+1].y),abs(p_vec[i+1].y-p_vec[i].y));
    Vec.push_back({val,{p_vec[i].num,p_vec[i+1].num}});
  }
  sort(p_vec.begin(),p_vec.end(),comp3);
  for(int i=0; i<N-1; i++){
    int val = min(abs(p_vec[i].z-p_vec[i+1].z),abs(p_vec[i+1].z-p_vec[i].z));
    Vec.push_back({val,{p_vec[i].num,p_vec[i+1].num}});
  }
}
 
int Find(int x){
  if(Parent[x]==x) return x;
  else return Parent[x] = Find(Parent[x]);
}
 
bool Same(int x, int y){
  if(Find(x)==Find(y)) return true;
  else return false;
}
 
int main() {
  cin >> N;
  for(int i=0; i<N; i++){
    int x,y,z;
    cin >> x >> y >> z;
    p_vec.push_back({i,x,y,z});
    Parent[i] = i;
  }
  
  Sort();
 
  sort(Vec.begin(),Vec.end());
  for(int i=0; i<Vec.size(); i++){
    int from = Vec[i].second.first;
    int to = Vec[i].second.second;
    int cost = Vec[i].first;
 
    if(Same(from,to)) continue;
 
    result += cost;
    Parent[Find(from)] = Find(to);
  }
 
  cout << result;
}

 

이게 제가 구현한 코드고 답을 맞춘 후 다른 사람들은 어떻게 구현했나 한 번 보고 참고해서 다시 구현해 봤습니다.

 

<수정한 소스 코드>

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 100000
 
using namespace std;
 
int N, Parent[MAX], result=0;
vector<pair<int,int>> X;
vector<pair<int,int>> Y;
vector<pair<int,int>> Z;
vector<pair<int,pair<int,int>>> Vec;
 
int Find(int x){
  if(Parent[x]==x) return x;
  else return Parent[x] = Find(Parent[x]);
}
 
bool Same(int x, int y){
  if(Find(x)==Find(y)) return true;
  else return false;
}
 
int main() {
  cin >> N;
  for(int i=0; i<N; i++){
    int x,y,z;
    cin >> x >> y >> z;
    X.push_back({x,i});
    Y.push_back({y,i});
    Z.push_back({z,i});
    Parent[i] = i;
  }
  
  sort(X.begin(),X.end());
  sort(Y.begin(),Y.end());
  sort(Z.begin(),Z.end());
 
  for(int i=0; i<N-1; i++){
    Vec.push_back({X[i+1].first-X[i].first,{X[i].second,X[i+1].second}});
    Vec.push_back({Y[i+1].first-Y[i].first,{Y[i].second,Y[i+1].second}});
    Vec.push_back({Z[i+1].first-Z[i].first,{Z[i].second,Z[i+1].second}});
  }
 
  sort(Vec.begin(), Vec.end());
 
  for(int i=0; i<Vec.size(); i++){
    int from = Vec[i].second.first;
    int to = Vec[i].second.second;
    int cost = Vec[i].first;
 
    if(Same(from,to)) continue;
 
    result += cost;
    Parent[Find(from)] = Find(to);
  }
 
  cout << result;
}

다른 사람들의 코드를 보고 느낀건 '아 왜 내가 굳이 하나의 벡터로 모두 해결하려고 했을까' 였습니다.

x, y, z 각각에 대한 벡터를 만들어서 하니 훨씬 코드도 깔끔하고 이해하기 쉬워보였습니다. 그리고 정렬을 해줬기 때문에 굳이 min과 abs를 쓸 필요가 없었습니다. 메모리와 시간 모두 크게 차이가 나지는 않지만 아래코드가 좀 더 시각적으로 보기 좋고 이해하기 쉬운 코드라고 생각합니다.

 

한 번에 해결해서 뿌듯했는데 다른 사람들의 코드를 보니 역시 아직 갈길이 먼 것 같습니다..