Gidhub BE Developer

[Programmers] 섬 연결하기

2018-10-09
goodGid

Problem

Problem URL : 섬 연결하기


[1] Answer Code (18. 10. 09)

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#define pii pair<int,int>
using namespace std;

bool visit[101];
vector<pii> vc[101];

int prim(int start){
    visit[start] = true;
    
    // 우선 순위 큐(최소 힙)
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    
    // 0번 정점을 시작점으로 한다.
    for (int i = 0; i < vc[start].size(); i++){
        // 정점과 가중치를 priority_queue에 넣어준다.
        int next = vc[start][i].first;
        int nextCost = vc[start][i].second;
        pq.push(pii(nextCost, next));
    }
    
    int ans = 0;
    while (!pq.empty()){
        int here = pq.top().second;
        int hereCost = pq.top().first;
        pq.pop();
        
        if (visit[here]) // 이미 방문한 정점은 무시한다.
            continue;
        visit[here] = true;
        ans += hereCost;
        
        // 다음 정점을 우선순위 큐에 넣어준다.
        for (int i = 0; i < vc[here].size(); i++){
            int there = vc[here][i].first;
            int thereCost = vc[here][i].second;
            pq.push(pii(thereCost, there));
        }
    }
    return ans;
}


int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    int size = (int) costs.size();
    
    for(int i=0; i<size; i++){
        int from = costs[i][0];
        int to = costs[i][1];
        int val = costs[i][2];
        vc[from].push_back(pii(to, val));
        vc[to].push_back(pii(from, val));
    }
    
    answer = prim(0);
    return answer;
}

Review

  • Prim 알고리즘을 사용했다.

Recommend

Index