[백준/Baekjoon] 1922 네트워크 연결 C++ :: MST & Kruskal, Prim

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

1922번: 네트워크 연결

---

1. Logic

최소 스패닝 트리 기본 문제

---

2. Code

Kruskal

#include <bits/stdc++.h>

using namespace std;

int v, e;

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

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 cost = graph[i].first;
        int start = graph[i].second.first;
        int end = graph[i].second.second;
        
        int x = find(start);
        int y = find(end);
        
        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[1001];
bool vis[1001];

int solve() {
    priority_queue<pair<int, int>> pq;
    
    vis[1] = true;
    for(int i = 0; i < graph[1].size(); i++) {
        pq.push({-graph[1][i].second, graph[1][i].first});
    }
    
    int weight = 0;
    
    while(!pq.empty()) {
        int cur = pq.top().second;
        int cost = -pq.top().first;
        
        pq.pop();
        
        if(vis[cur]) continue;
        
        vis[cur] = true;
        weight += cost;
        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.tie(0); cout.tie(0);
    
    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 << solve();
}

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

728x90