문제 출처

1. 문제설명

  • 행성 T에서 N개의 행성 간에 플로우를 설치하려고 한다.
  • 모든 행성을 연결하면서 플로우 관리 비용을 최소화 하려 한다.

  • 행성 i와 행성 j사이의 플로우 관리비용은 $C_ij$이며, i = j인 경우 항상 0이다.

  • 문제 분류
    • Graph, MST


2. 알고리즘 설계

  • 최소신장트리 문제이다.
  • 간선과 간선 간 비용을 입력받고 정렬한다.
  • 두 노드의 부모가 같지 않다면, 연결해주면 된다.
  • 결과값이 int 범위를 초과할 수 있으니, long long 형으로 선언해야 한다.


3. 전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
int parent[1001];
int cost[1001][1001];
vector<pair<int, pair<int, int>>> edge;

int FindParent(int x){
    if(x == parent[x])
        return x;
    
    return parent[x] = FindParent(parent[x]);
}

bool SameParent(int x, int y){
    x = FindParent(x);
    y = FindParent(y);

    if(x == y)
        return true;
    return false;
}

void Merge(int x, int y){
    x = FindParent(x);
    y = FindParent(y);

    if(x == y)
        return;
    parent[x] = y;
}

int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    // input
    cin >> n;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> cost[i][j];
        }
    }    
    
    // init
    for(int i = 1; i <= n; i++) 
        parent[i] = i;

    // edge
    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            edge.push_back(make_pair(cost[i][j], make_pair(i, j)));
        }
    }

    // Make MST
    long long ans = 0;
    sort(edge.begin(), edge.end());

    for(int i = 0; i < edge.size(); i++){
        if(!SameParent(edge[i].second.first, edge[i].second.second)){
            ans += edge[i].first;
            Merge(edge[i].second.first, edge[i].second.second);
        }
    }

    cout << ans << '\n';
}