79. 원더랜드 [Prim 알고리즘 이용]

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

문제는 비공개

 

풀이 

- 최소비용스패닝 트리 구성

- 노드를 한개씩 추가해가면서 그 노드들에 인접한 간선들에 대한 비용을 우선순위큐에 넣는다.

- 우선순위큐는 최소힙 구조로 원소를 하나씩 팝하면서 들어온 비용 중 가장 작은 비용을 res에 더한다.

- 간선의 연결정보는 무방향그래프이기 때문에 vector<pair<int, int>>를 이용해서 연결정보를 저장한다.

- 한번 방문한 정점은 간선의 값이 최소여도 방문하면 안되기 때문에 ch배열로 체크한다. 

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int ch[30];

//79. 원더랜드(Prim MST 알고리즘)
//최소비용 트리

struct Edge{
    int e; //정점
    int val; //값
    Edge(int a, int b){
        e=a;
        val=b;
    }
    bool operator<(const Edge &b)const{
        return val>b.val; //최소힙
    }
};


int main(){
    priority_queue<Edge> Q;
    vector<pair<int, int> > map[30];
    int i, n, m, a, b, c, res=0;
    scanf("%d %d", &n, &m); //정점, 간선
    for(i=1;i<=m;i++){
        //무방향
        map[a].push_back(make_pair(b,c)); //a-b 연결
        map[b].push_back(make_pair(a,c)); //b-a 연결
    }
    Q.push(Edge(1,0));
    while(!Q.empty()){
        Edge tmp=Q.top();
        Q.pop(); //(1,0) Pop
        int v=tmp.e; //1
        int cost=tmp.val; //0
        
        //큐에서 나온 정점이 트리에 현재 속해있는 원소인지?(방문했는지)
        if(ch[v]==0){
            res+=cost;
            ch[v]=1;
            for(i=0;i<map[v].size();i++){
                Q.push(Edge(map[v][i].first, map[v][i].second));
            }
        }
    }
    printf("%d\n", res);
    return 0;
}