[해커랭크] Prim's (MST) : Special Subtree (C++)

문제 링크: www.hackerrank.com/challenges/primsmstsub/problem?utm_campaign=challenge-recommendation&utm_medium=email&utm_source=24-hour-campaign

Prim's (MST) : Special Subtree | HackerRank

1. 주의할 점

- MST중에서 프림 알고리즘에 대해서 알고 있어야 한다(Edge수가 Node수보다 월등히 많을 때 유리. 반대의 경우, 크루스칼이 유리)

 

2. 구현

- 간선에 대한 정보를 V[] 벡터에 모두 저장한다

- 간선의 가중치를 기준으로 오름차순으로 정렬되는 우선순위큐 PQ를 생성한다

- 프림 알고리즘을 시작으로, 일반 Queue에 Start 번호 삽입 + Visit[Start]=true로 설정한다

- 일반 Queue가 빌때까지 진행되며(혹은 간선의 개수가 N-1개가 될때까지 진행), Queue에서 꺼낸 Node와 연결된 모든 간선 중에서 반대편 Node를 아직 방문하지 않은 간선만 PQ에 넣는다

- PQ에서 간선을 뽑으면서, 아직 방문하지 않은 Node의 경우 해당 간선을 MST에 추가하고 가중치를 Result에 더한다

 

#include <bits/stdc++.h>

using namespace std;

vector<string> split_string(string);
bool visit[3001]={false,};
struct info{
    int idx,val;
};
struct cmp{
    bool operator()(info &a, info &b){
        return a.val > b.val;
    }
};
info tmp;
vector<info> v[3001];
// Complete the prims function below.
int prims(int n, vector<vector<int>> edges, int start) {
    for(int i=0;i<edges.size();i++){
        int a = edges[i][0];
        int b = edges[i][1];
        int val = edges[i][2];
        tmp.val = val;
        tmp.idx = b;
        v[a].push_back(tmp);
        tmp.idx=a;
        v[b].push_back(tmp);
    }
    
    priority_queue<info,vector<info>,cmp> pq;
    queue<int> q;
    int result=0;
    q.push(start);
    visit[start]=true;
    while(!q.empty()){
        int cidx = q.front();
        q.pop();
        for(int i=0;i<v[cidx].size();i++){
            int next = v[cidx][i].idx;
            if(visit[next]) continue;
            int nv = v[cidx][i].val;
            tmp.idx = next;
            tmp.val = nv;
            pq.push(tmp);
        }
        while(!pq.empty()){
            cidx = pq.top().idx;
            int cv = pq.top().val;
            pq.pop();
            if(visit[cidx]) continue;
            visit[cidx]=true;
            result+=cv;
            q.push(cidx);
            break;
        }       
    }
    return result;
}