백준 1197 최소 스패닝 트리

문제 링크 : https://www.acmicpc.net/problem/1197

문제 설명

최소스패닝트리(최소신장트리,MST)는 그래프 내의 모든 정점을 연결하고 (정점이 n개면 간선은 n-1) 사이클이 없는 그래프 중 그래프의 간선 가중치 합이 최소가 되는 트리를 최소스패닝트리(최소신장트리)라고 한다.
이 최소스패닝트리 문제들은 프림 알고리즘과 크루스칼 알고리즘을 사용하여 풀 수 있다.

프림 알고리즘(prim's algorithm)

프림 알고리즘은 최소 신장 트리에 연결된 정점 주변에 있는 간선의 가중치 중 가장 작은 것을 골라 최소 신장 트리를 만드는 방법이고, 힙을 사용한다는 특징이있다.

크루스칼 알고리즘(Kruskal's algorithm)

크루스칼 알고리즘은 그래프 내의 모든 간선의 가중치를 확인하고 가장 작은 가중치부터 확인해서 최소 신장 트리를 만드는 방법이고, 유니온 파인드를 사용한다는 특징이 있다.

나는 이 문제를 비교적 코드수가 적은 프림 알고리즘을 사용하여 풀었고, 추후 MST 문제들을 만난다면 백준 MST 문제들은 프림 / 프로그래머스 MST문제들은 크루스칼 알고리즘을 사용하여 풀어볼 예정이다.
나는 이문제를 가중치가 적은 정점이 연결될 때, 가중치 값의 합을 더하여 결과를 구했다.

코드

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
vector<pair<int, int> >v[10001]; 
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int, int> > >pq;
bool visited[10001];
int sum;
 
void prim(int a)            // 프림 알고리즘 
{
    visited[a] = true;           // 시작 노드 방문  처리
    for (int i = 0; i < v[a].size(); i++)       // Node a와 연결된 방문 안한 다른 노드들 우선순위 큐에 넣기
    {
        if(!visited[v[a][i].second])
        {
            pq.push(make_pair(v[a][i].first,v[a][i].second));
        }
    }
    while (!pq.empty())
    {
        pair<int,int> pp = pq.top();
        pq.pop();
        if (!visited[pp.second])        // 방문하지 않은 노드 중 가장 가중치가 적은거 발견 시 그 노드를 인자값으로 prim함수 호출 후 함수 끝내기
        {
            sum+=pp.first;
            prim(pp.second);
            return ;                
        }
    }
}
int main()
{
    int a, b;
    cin >> a >> b;
    for (int i = 1; i <= b; i++)        // 정점 연결과 가중지 입력.
    {
        int a1, a2, a3;                 // 정점 1, 정점 2, 가중치
        cin >> a1 >> a2 >> a3;
        v[a1].push_back(make_pair(a3,a2));
        v[a2].push_back(make_pair(a3,a1));
    }
    prim(1);                            // 첫번째 노드를 인자값에 넣어 prim 함수 호출
    cout << sum;
    return 0;
}