[BOJ/C++] 16398 행성 연결

https://www.acmicpc.net/problem/16398

문제
홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다.

두 행성 간에 플로우를 설치하면 제국의 함선과 무역선들은 한 행성에서 다른 행성으로 무시할 수 있을 만큼 짧은 시간만에 이동할 수 있다. 하지만, 치안을 유지하기 위해서 플로우 내에 제국군을 주둔시켜야 한다.

모든 행성 간에 플로우를 설치하고 플로우 내에 제국군을 주둔하면, 제국의 제정이 악화되기 때문에 황제 윤석이는 제국의 모든 행성을 연결하면서 플로우 관리 비용을 최소한으로 하려 한다.

N개의 행성은 정수 1,…,N으로 표시하고, 행성 i와 행성 j사이의 플로우 관리비용은 Cij이며, i = j인 경우 항상 0이다.

제국의 참모인 당신은 제국의 황제 윤석이를 도와 제국 내 모든 행성을 연결하고, 그 유지비용을 최소화하자. 이때 플로우의 설치비용은 무시하기로 한다.

입력
입력으로 첫 줄에 행성의 수 N (1 ≤ N ≤ 1000)이 주어진다.

두 번째 줄부터 N+1줄까지 각 행성간의 플로우 관리 비용이 N x N 행렬 (Cij), (1 ≤ i, j ≤ N, 1 ≤ Cij ≤ 100,000,000, Cij = Cji, Cii = 0) 로 주어진다.

출력
모든 행성을 연결했을 때, 최소 플로우의 관리비용을 출력한다.

문제 정리

모든 행성을 연결하고 유지비용을 최소화 해야한다. 따라서 최소 신장 트리(MST)를 사용하는 문제인걸 알 수 있다. 1 ≤ N ≤ 1000 이므로 최대 1000*1000 행렬이 만들어 질 수 있다. 각 행성간 플로우 관리 비용이 최대 100,000,000이므로 다 연결했을 때 int의 범위를 넘을 수 있다는 것을 주의하자. 최소 신장 트리

코드

#include <bits/stdc++.h>
using namespace std;

vector<tuple<int,int,int>> adj;
int parent[1002];

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

bool Union(int x, int y)
{
    x = find(x);
    y = find(y);
    if(x==y)
        return false;
    if(x<y)
        parent[y] = x;
    else
        parent[x] = y;
    return true;
}

int main()
{
    int n;
    cin >> n;
    for(int from=1; from<=n; from++)
    {
        int value;
        for(int to=1; to<=n; to++)
        {
            cin >> value;
            //0을 입력했을땐 그냥 건너뛴다
            if(from == to)
                continue;
            adj.push_back({value,from,to});
        }
    }

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

    for(int i=1; i<=n; i++)
        parent[i]=i;
    
    long long res=0; //결과의 자료형 생각하기
    int cnt=0;
    for(auto nxt: adj)
    {
        if(cnt == n-1)
            break;
        int cost,a,b;
        tie(cost,a,b) = nxt;
        if(Union(a,b))
        {
            res+=cost;
            cnt++;
        }
    }
    cout << res;
}

크루스칼 알고리즘을 통해 구현했다. 사실 최소 신장 트리를 구현할 수 있다면 쉽게 해결할 수 있을 것이다.

문제를 보고 최소 신장 트리를 이용한 해결법이 떠오르도록 연습하는 것이 중요하다고 생각한다.