[백준/Baekjoon] 1197 최소 스패닝 트리 C++ :: MST & Kruskal, Prim

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

1197번: 최소 스패닝 트리

---

1. Logic

최소 스패닝 트리 기본문제

 

오늘 MST(Minimum Spanning Tree) 최소스패닝 트리를 공부해서 풀이 방법인 크루스칼, 프림 두방식 모두 풀이해봤다.

---

2. Code

Kruskal

#include <bits/stdc++.h>

using namespace std;

int v, e;

vector<pair<int, pair<int, int>>> graph;
int parent[10001];

int find(int x) {
    if(parent[x] == x) return x;
    
    return parent[x] = find(parent[x]);
}

int solve() {
    int weight = 0;
    
    for(int i = 0; i < e; i++) {
        int s = graph[i].second.first;
        int e = graph[i].second.second;
        int cost = graph[i].first;
        
        int x = find(s);
        int y = find(e);
        
        if(x == y) continue;
        
        if(x < y) parent[y] = x;
        else parent[x] = y;
        
        weight += cost;
    }
    
    return weight;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> v >> e;
    
    for(int i = 0; i < e; i++) {
        int start, end, cost;
        cin >> start >> end >> cost;
        
        graph.push_back({cost, {start, end}});
    }
    
    sort(graph.begin(), graph.end());
    
    for(int i = 1; i <= v; i++) {
        parent[i] = i;
    }
    
    cout << solve();
}

Prim

#include<bits/stdc++.h>

using namespace std;

int v, e;
vector<pair<int, int>> graph[10001];
bool vis[10001];

int prim() {
    priority_queue<pair<int, int>> pq;
    
    int weight = 0;
    
    vis[1] = true;
    for(int i = 0; i < graph[1].size(); i++) {
        pq.push({-graph[1][i].second, graph[1][i].first});
    }
    
    while(!pq.empty()) {
        int cur = pq.top().second;
        int cost = -pq.top().first;
        
        pq.pop();
        if(vis[cur]) continue;
        
        weight += cost;
        vis[cur] = true;
        
        for(int i = 0; i < graph[cur].size(); i++) {
            pq.push({-graph[cur][i].second, graph[cur][i].first});
        }
        
    }
    return weight;
}

int main() {
    ios_base::sync_with_stdio(false);
    
    cin >> v >> e;
    
    for(int i = 0; i < e; i++) {
        int start, end, cost;
        cin >> start >> end >> cost;
        
        graph[start].push_back({end, cost});
        graph[end].push_back({start, cost});
    }
    
    cout << prim();
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90