[백준][C++] 2887 행성 터널

 

 

 

알고리즘 종류

    - MST

 

 

 

사고 과정

    - 첫 번째 시도(메모리 초과)

        1. 조합을 이용해서 두 정점들 사이의 비용 구하기 (완전 그래프)

        2. 비용을 기준으로 오름차순 정렬

        3. Union-Find으로 MST 구하기

 

    - 무엇이 문제인가?

        * 완전 그래프를 사용하면 메모리 초과가 발생한다. n은 최대 10^5이다. 완전 그래프로 만들면, (n-1)(n-2)/2이므로 10^9가 넘는다. 10^6이 1mb인 것을 감안하면, 1000mb가 넘는다.

        * 완전 그래프를 사용하지 않고 MST를 만들어야 한다. 여기 정점들은 x축, y축, z축으로 따로 표현될 수 있다. 즉, x축, y축, z축에서 각각 거리를 구해서 최소 거리로 정렬하여 MST를 만들면 될 것이다. 그러면, 공간 복잡도는 3n이 될 것이다.

 

    - 두 번째 시도

        1. x축 기준으로 오름차순 정렬하여  i번째 정점과 i+1정점 간의 거리를 구하여 vector에 저장한다.

        2. y축 기준으로 오름차순 정렬하여  i번째 정점과 i+1정점 간의 거리를 구하여 vector에 저장한다.

        3. z축 기준으로 오른차순 정렬하여  i번째 정점과 i+1정점 간의 거리를 구하여 vector에 저장한다.

        4.  vector를 거리 기준으로 오름차순 정렬한다.

        5. Union-Find으로 MST 구하기

    

 

 

구현(C++)

    - 첫 번째 시도(메모리 초과)

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
 
using namespace std;
 
int n;
int answer;
 
int isSelected[100001];
int parents[100001];
 
typedef struct Location{
    int x, y, z;
};
 
typedef struct Edge{
    int from,to,cost;
};
 
vector<Location> v;
vector<Edge> edges;
vector<int> tmp_v;
 
bool cmp(Edge a, Edge b){
    return a.cost < b.cost;
}
 
// 거리 비용 구하기
void distance(){
    
    int a = tmp_v[0];
    int b = tmp_v[1];
    
    int dist = min(min( abs(v[a].x - v[b].x), abs(v[a].y - v[b].y)), abs(v[a].z- v[b].z));
    
    Edge e;
    e.from = a;
    e.to = b;
    e.cost = dist;
    
    edges.push_back(e);
    
}
 
// 두 정점 선택하기
void measure_distance(int cur){
    // 두 정점이 선택되면 거리 비용 구하기
    if(tmp_v.size() == 2){
        distance();
        return;
    }
    
    for(int i=cur; i<n; i++){
        if(isSelected[i])continue;
        isSelected[i] = 1;
        tmp_v.push_back(i);
        measure_distance(i);
        tmp_v.pop_back();
        isSelected[i] = 0;
    }
}
 
int getParent(int a){
    if(parents[a] == a)    return a;
    return getParent(parents[a]);
}
 
void unionParents(int a, int b){
    a = getParent(a);
    b = getParent(b);
    
    if(a < b){
        parents[b] = a;
    } else{
        parents[a] = b;
    }
}
 
bool findParent(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if(a == b) return true;
    else return false;
}
 
void kruskal(){
    
    for(int i=0; i<n; i++){
        parents[i] = i;
    }
    
    int sum = 0;
    for(int i=0; i<edges.size(); i++){
        if(!findParent(edges[i].from-1, edges[i].to-1)){
            sum += edges[i].cost;
            unionParents(edges[i].from-1, edges[i].to-1);
        }
    }
    
    answer = sum;
    
}
 
void solution(){
    // 조합을 이용해서 두 정점 선택하고 거리 비용 계산
    measure_distance(0);
    // 거리 비용으로 오름차순 정렬
    sort(edges.begin(), edges.end(), cmp);
    // 크루스칼 알고리즘
    kruskal();
}
 
 
int main(void){
    
    cin >> n;
    
    for(int i=0; i<n; i++){
        int x, y, z;
        cin >> x >> y >> z;
        
        Location planet;
        planet.x = x;
        planet.y = y;
        planet.z = z;
        v.push_back(planet);
    }
    
    solution();
    
    cout << answer;
    
}
 
 

 

 

    - 두 번째 시도

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
 
using namespace std;
 
int n;
int answer = 0;
int parents[100001];
 
 
struct Planet{
    int id, x, y, z;
};
 
struct Edge{
    int from, to, cost;
};
 
vector<Planet> planets;
vector<Edge> edges;
 
// 정렬을 위한 비교 함수
bool cmp(Edge a, Edge b){
    return a.cost < b.cost;
}
 
bool cmpx(Planet a, Planet b){
    return a.x < b.x;
}
 
bool cmpy(Planet a, Planet b){
    return a.y < b.y;
}
 
bool cmpz(Planet a, Planet b){
    return a.z < b.z;
}
 
 
int getParent(int a){
    if(a == parents[a]) return a;
    return getParent(parents[a]);
}
 
bool isCycle(int a, int b){
    a = getParent(a);
    b = getParent(b);
    
    if(a == b) return true;
    else return false;
}
 
void unionParents(int a, int b){
    a = getParent(a);
    b = getParent(b);
    
    if(a < b){
        parents[b] = a;
    }else{
        parents[a] = b;
    }
}
 
 
void kruskal(){
    int sum = 0;
    for(int i=0; i<edges.size(); i++){
        if(!isCycle(edges[i].from, edges[i].to)){
            unionParents(edges[i].from, edges[i].to);
            sum += edges[i].cost;
        }
    }
    answer = sum;
}
 
 
void solution(){
    
    // x축 기준, y축 기준, z축 기준으로 정렬하고 인접한 정점들 사이 거리 계산
    sort(planets.begin(), planets.end(), cmpx);
    for(int i=0; i<planets.size()-1; i++){
        Edge e;
        e.from = planets[i].id;
        e.to = planets[i+1].id;
        e.cost = abs(planets[i].x - planets[i+1].x);
        edges.push_back(e);
    }
    
    sort(planets.begin(), planets.end(), cmpy);
    for(int i=0; i<planets.size()-1; i++){
        Edge e;
        e.from = planets[i].id;
        e.to = planets[i+1].id;
        e.cost = abs(planets[i].y - planets[i+1].y);
        edges.push_back(e);
    }
    
    sort(planets.begin(), planets.end(), cmpz);
    for(int i=0; i<planets.size()-1; i++){
        Edge e;
        e.from = planets[i].id;
        e.to = planets[i+1].id;
        e.cost = abs(planets[i].z - planets[i+1].z);
        edges.push_back(e);
    }
    
    // 거리 비용으로 정렬
    sort(edges.begin(), edges.end(), cmp);
    // 크루스칼 알고리즘
    kruskal();
}
 
int main(void){
    
    cin >> n;
    
    for(int i=0; i<n; i++){
        int x, y, z;
        cin >> x >> y >> z;
        
        Planet p;
        p.id = i;
        p.x = x;
        p.y = y;
        p.z = z;
        planets.push_back(p);
        
        parents[i] = i;
    }
    
    solution();
    
    cout << answer;
}
 
 

 

 

 

시행착오

    - x축, y축, z축으로 정렬하고 인접한 정점 사이의 거리를 구하여 정렬하는 것이 과연 최소 스패닝 트리를 만드는지 의문이 들었다. 예를 들어, x축 기준으로 정렬하는 것을 보면 아래와 같다.

 

x축에 놓인 상태 : A(-11) == B(1) == C(2) == D(14), ==는 축

edges에 저장된 데이터 : {AB:12, BC:1, CD:12}

 

이렇게 인접한 정점들 간의 비용만 구한다고? 그러면 A에서 C로 가는 비용이 A에서 B로 가고 B에서 C로 가는 비용의 합보다 작을 경우는 있다면 어떻게 할 것인가? 잘 몰라서 생각한 의문이었다. A==B==C 비용과 A==C 비용이 같다. 즉, A==C 비용이 필요하면, A==B==C를 거쳐도 비용은 똑같다. 그래서 인접한 정점들 간의 비용을 구해서 정렬하고 MST를 구하면 된다.