[백준/C++] 최소 스패닝 트리

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 최소 스패닝 트리를 구하는 문제로 모든 노드가 연결되어 있어야 한다.

 

단순히 비용을 기준으로 정렬을 한 다음 두 노드가 연결될 경우에 방문 처리를 하면 떨어진 섬과 같은 경우가 발생하기 때문에 방법을 생각해 봤다.

 

Union-Find를 사용하면 떨어진 경우를 제외할 수 있을 것 같았지만,  굳이 그럴 필요가 없을 것 같아서 그냥 priority_queue를 이용해 단순하게 풀었다. (나중에 찾아보니 Prim 알고리즘 방식이었다..)

 

이 priority_queue는 비용을 기준으로 오름차순 정렬 되어 있다.

 

먼저 모든 노드를 방문해야 하므로 탐색을 처음 시작할 노드를 고른다.

 

그리고 그 노드를 방문처리한다음 연결된 간선 중에서 아직 방문하지 않은 간선을 priority_queue에 추가한다.

 

이제 priority_queue에서 노드를 꺼내고 만약 아직 방문한 적이 없다면, 마찬가지로 탐색을 해 간선을 priority_queue에 추가 한다.

 

탐색이 끝난 후 간선의 비용을 출력하면 된다.

 

 

​

[아이디어 정리]

1. priority_queue는 비용을 기준으로 오름차순 정렬되어 있다.
2. 처음 방문할 노드를 정하고 queue에 넣는다.
3. 이후 queue에서 꺼낸 노드가 아직 방문한 적이 없다면, 방문 처리를 하고 그 노드와 연결된 간선들을 queue에 추가한다.
4. 탐색이 모두 끝난 후 계산된 최소 비용을 출력한다.

 

 

 

Code

 

 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

struct cmp {
    bool operator ()(pair<int,long long> a, pair<int, long long> b)
    {
        return a.second>b.second;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int V,E;
    cin >> V>>E;
    int a, b;
    long long v;
    vector<vector<pair<int, long long>>> graph(V + 1);
    for (int t = 0; t < E; t++) {
        cin >> a >> b >> v;
        graph[a].push_back(make_pair(b, v));
        graph[b].push_back(make_pair(a, v));
    }
    vector<bool> visited(V + 1, false);
    priority_queue <pair<int, long long>, vector<pair<int, long long>>, cmp> q;
    pair<int, long long> np;
    long long ans = 0;
    q.push(make_pair(1, 0));
    while (!q.empty()) {
        np = q.top();
        q.pop();
        if (!visited[np.first]) {
            ans += np.second;
            visited[np.first] = true;
            for (int i = 0; i < graph[np.first].size(); i++) {
                if (!visited[graph[np.first][i].first]) {
                    q.push(graph[np.first][i]);
                }
            }
        }
    }
    cout << ans;


    return 0;
}

 

---

문제가 복잡한 문제가 아니라서 MST에 대해 잘 이해하고 있으면 쉽게 풀 수 있는 문제였다.

 

https://www.acmicpc.net/problem/1197