[백준][C++] 16398 행성 연결

16398. 행성 연결
문제 풀이

16398번: 행성 연결

 

갑자기 N x N 행렬이 나와서 당황했지만... 문제를 천천히 알고보니 각 노드들을 서로 서로 잇는 간선의 가중치값이 있는 행렬이었고...

 

이런 구조는 프림 알고리즘에서 잘 볼 수 있는 구조이다!

만약 이런 트리가 있다고 한다면, 프림 알고리즘에서는...

이렇게 한 노드를 중심으로 연결된 노드와 그 간선의 가중치를 저장해주기 때문에!!

가중치를 저장한 행렬과 비슷하다고 볼 수 있었다.

 

그래서 프림 알고리즘을 이용해 풀어봤다.

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

// 가중치를 저장하는 2차원 배열
vector<int> weights[1000];
// 선택했는지 체크하는 배열
bool visited[1000];
long long int result = 0;

int main()
{
    int vCnt;
    cin >> vCnt;

    for (int i = 0; i < vCnt; i++)
    {
        weights[i].resize(vCnt);

        for (int j = 0; j < vCnt; j++)
        {
            cin >> weights[i][j];
        }
    }

    priority_queue<pii, vector<pii>, greater<pii>> pQueue;
    pQueue.push({ 0, 0 });

    // 프림 알고리즘
    while (vCnt)
    {
        int cost = pQueue.top().first;
        int node = pQueue.top().second;
        pQueue.pop();

        // 연결되지 않은 노드들만
        if (!visited[node])
        {
            visited[node] = true;
            result += cost;
            vCnt--;

            for (int i = 0; i < weights[node].size(); i++)
            {
                if (!visited[i])
                {
                    pQueue.push({ weights[node][i], i });
                }
            }
        }
    }

    cout << result;
}

N x N 2차원 배열이 나와 어려워 보였지만, 사실은 프림 알고리즘에 대한 힌트였고, 그렇게 어렵지 않았던 문제!