[프로그래머스] 섬연결하기 [cpp]

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42861

핵심

프림과, scala 알고리즘 존재하지만 프림 선택
모든 노드 간의 비용을 기록
cost를 기준으로 오름차순으로 정렬
시작 지점에서 cost가 제일 낮은 곳으로 이동함.
이동한 곳을 방문등록 하고 현재 node에 인접한 모든 곳을 다음행선지로 정하나,
행선지가 이미 방문한 곳이면 제외.
행선지가 없을때까지 반복.

#include <iostream>
#include <queue>
#include <tuple>
#include <vector>

using namespace std;
int solution(int n, vector<vector<int>> costs) {
    // 인접 리스트 생성
    vector<vector<pair<int, int>>> graph(n);
    // 이때 모든 방향의 그래프로 코스트를 삽입
    for (const auto &cost : costs) {
        int u = cost[0], v = cost[1], weight = cost[2];
        // 1 -> 2 비용 -> 2
        graph[u].emplace_back(v, weight); // 1 -> 2번으로 갈떄 비용 2 기록
        graph[v].emplace_back(u, weight); // 2 -> 1번으로 갈떄 비용 2 기록
    }

    // Prim 알고리즘
    // 첫번째 인자로 먼저 정렬하고 이후에 인자로 오름차순 정렬;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    vector<bool> visited(n, false);
    int totalCost = 0;

    // 시작 노드(0번)를 추가
    pq.emplace(0, 0); // (비용, 노드)

    while (!pq.empty()) {
        auto [cost, node] = pq.top();
        pq.pop();

        if (visited[node])
            continue;
        visited[node] = true;
        totalCost += cost;

        // 현재 노드에서 연결된 간선을 큐에 추가
        for (const auto &[nextNode, nextCost] : graph[node]) {
            // 하지만 이미 방문한 노드라면 제외
            if (!visited[nextNode]) {
                pq.emplace(nextCost, nextNode);
            }
        }
    }

    return totalCost;
}