백준 16398번: 행성 연결

🔗 문제 해석

 

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

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

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

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

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

 

 

💭 풀이 과정

행성을 정점으로 봤을 때 모든 행성을 최소 비용으로 관리한다? 

그렇다면 최소 스패닝 트리 (MST)이고 크루스칼이나 프림으로 풀 수 있다. 

문제를 잘 읽고 유형만 유추한다면 간단하게 풀 수 있는 골드4 문제였다.

 

 

주의사항

문제 조건에서 행성의 수가 1000개이고, 플로우 관리 비용의 100,000,000 이다. 

1000 x 1000 x 100,000,000이면 cost가 int 범위를 넘어가기 때문에 long long 지정해주자.

 

🚀 전체 소스

 

유니온파인드 복습 겸 크루스칼로 풀었다.

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

vector<int> parent;

struct Node
{
    int cost, from, to;
};

struct cmp
{
    bool operator()(const Node& a, const Node& b)
    {
        return a.cost > b.cost;
    }
};

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

bool merge(const int a, const int b)
{
    int ra = find(a);
    int rb = find(b);

    if(ra == rb) return false;

    if(ra < rb)
    {
        parent[ra] += parent[rb];
        parent[rb] = ra;
    }
    else
    {
        parent[rb] += parent[ra];
        parent[ra] = rb;
    }

    return true;
}

int main()
{
    long long answer = 0L;
    int N;
    int count = 0, cost;

    priority_queue<Node, vector<Node>, cmp> pq;

    cin >> N;
    for(int i=0; i<N; ++i)
    {
        for(int j=0; j<N; ++j)
        {
            cin >> cost;
            pq.push({cost, i, j});
        }
    }

    parent.resize(N, -1);
    while(!pq.empty())
    {
        auto front = pq.top(); pq.pop();

        if(merge(front.from, front.to))
        {
            answer += front.cost;
            if(++count == N-1)
                break;
        }
    }

    std::cout << answer;

    return 0;
}