백준 2887 행성 터널 쉬운 풀이 (C++/CPP)

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

아이디어

• 모든 행성을 터널로 연결 >> MST
  • Kruscal 사용해서 MST 구하자
• 간선의 개수 : E = N(N+1)/2 = 1e10/2 = 5e9
  • MST 시간복잡도 : O(ElgE) > 시간초과
  • 간선을 모두 넣는 경우에는 시간초과가 발생
• 문제 중 비용 = min(x, y, z)을 이용
  • x,y,z 좌표의 차이를 각각 넣고, 이중 최소값만 사용하면됨
    • 크루스칼에서 자연스럽게 최소의 간선만 적용될 것임
  • 모든 노드의 간선을 넣지말고. 정렬한뒤 근접한 것만 적용
    • 어짜피 최소값만 MST에서 살아남게됨
    • 그러므로 정렬 시킨다음에 인접한 것이 가장 작은 값

시간복잡도 계산

• x,y,z 좌표에 대해서 각각 정렬 : O(3 * NlgN)
  • 인접한 노드에 대해서 간선 추가 : O(3 * N)
  • MST 시간복잡도 : ElgE
    • 간선의 개수(E): 3N
    • 3Nlg3N
  • 총합 : O(3NlgN + 3N + 3Nlg3N) = O(NlgN)

인트 계산

• 간선 의 길이 최대값 : 2e9 > INT 가능
• 최소비용 : 2e9 *N-1 >> long long 사용

코드

#include <iostream>
#include <tuple>
#include <algorithm>
#include <vector>
#include <cmath>
 
using namespace std;
typedef tuple<int, int, int> ti3;
typedef pair<int, int> pi2;
typedef long long ll;
 
vector<ti3> edge;
int p[100010];
vector<pi2> xnode;
vector<pi2> ynode;
vector<pi2> znode;
 
int N;
 
int find(int v) {
    if(p[v] < 0) return v;
    return p[v] = find(p[v]);
}
 
bool is_diff_group(int v1, int v2) {
    v1 = find(v1); v2 = find(v2);
    if(v1 == v2) return 0;
    
    if(p[v1] == p[v2]) p[v1]--;
    
    if(p[v1] < 0) p[v2] = v1;
    else p[v1] = v2;
    return 1;
    
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    fill(p, p+100010, -1);
    cin >> N;
    
    // 각 좌표 넣기
    // 이때 노드 인덱스랑 같이 넣어줌 정렬후 확인하기 위해
    for(int i=0; i<N; i++) {
        int ex, ey, ez;
        cin >> ex >> ey >> ez;
        xnode.push_back(make_pair(ex, i));
        ynode.push_back(make_pair(ey, i));
        znode.push_back(make_pair(ez, i));
    }
    
    // 간선수 줄이기위해 정렬
    sort(xnode.begin(), xnode.end());
    sort(ynode.begin(), ynode.end());
    sort(znode.begin(), znode.end());
    
    // 인접한 노드를 엣지에 추가
    for(int i=0; i<N-1; i++) {
        edge.push_back({abs(xnode[i].first - xnode[i+1].first),xnode[i].second,xnode[i+1].second});
        edge.push_back({abs(ynode[i].first - ynode[i+1].first),ynode[i].second,ynode[i+1].second});
        edge.push_back({abs(znode[i].first - znode[i+1].first),znode[i].second,znode[i+1].second});
    }
    
    // 간선들 정렬
    sort(edge.begin(), edge.end());
    
    int cnt=0;
    ll ans=0;
    // Kruscal 수행
    for(int i=0; i<edge.size(); i++) {
        int cost, a,b; tie(cost,a,b) = edge[i];
        if(!is_diff_group(a,b)) continue;
        
        cnt++;
        ans += cost;
        if(cnt==N-1) break;
    }
    
    cout << ans << '\n';
    
    
    return 0;
}
 

문제유형

• MST - 간선의 특수 조건
  • 간선의 비용이 특수한 경우
  • 일반적으로 하면 간선의 개수가 많아서 시간초과 발생
  • 간선의 조건 활용해 그리디하게 사용 가능