[프로그래머스 LV3] - 섬 연결하기(prim's algorithm) c++

문제

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

프로그래머스

접근방법

prim's algorithm을 사용해 풀었다.

 

문제에서 vertice 숫자의 범위를 제시하지 않아

adjecency list를 사용하기 애매해서, adjencency map을 사용했다.

코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>

using namespace std;

class Edge{
public:
    int to;
    int weight;
    
    bool operator<(const Edge& other) const{
        return weight > other.weight;
    }
};

map<int, vector<Edge>> adj_map;
map<int, bool> visit;
priority_queue<Edge> pq;


int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    
    for (const auto& c : costs) {
        Edge edge1; edge1.to = c[1]; edge1.weight = c[2];
        Edge edge2; edge2.to = c[0]; edge2.weight = c[2];
        vector<Edge> temp1 = adj_map[c[0]];
        vector<Edge> temp2 = adj_map[c[1]];
        temp1.push_back(edge1); temp2.push_back(edge2);
        adj_map[c[0]] = temp1;
        adj_map[c[1]] = temp2;
    }
    visit[costs[0][0]] = true;
    for(const auto& start : adj_map[costs[0][0]]) {
        pq.push(start);
    }
    
    while(!pq.empty()) {
        Edge edge = pq.top();
        pq.pop();
        
        if (!visit[edge.to]) {
            answer += edge.weight;
            visit[edge.to] = true;
            for (const auto& adj : adj_map[edge.to]) {
                pq.push(adj);
            }
        }
    }
    
    
    
    return answer;
}

개선할 점

class안에 operator를 정의해 놓으면,

priority queue 선언할 때 아주 간편하게 할 수 있다.

 

유용하게 쓰일 것 같다.