[백준/Baekjoon] 1647 도시 분할 계획 C++ :: MST & Kruskal, Prim

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

1647번: 도시 분할 계획

---

1. Logic

최소 스패닝 트리 기본 문제.

문제를 읽어보면 분리된 두 마을의 길들은 없앤다고 했기 때문에

1. 모든 마을을 연결하는 최소 스패닝 트리를 구하고

2. 스패닝 트리를 구성하는 원소값 중 최댓값을 원소의 합에서 빼서 정답을 도출한다.

---

2. Code

Kruskal

#include <bits/stdc++.h>

using namespace std;

int v, e;

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

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

int solve() {
    int weight = 0;
    int maxWeight = 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;
        
        maxWeight = max(maxWeight, cost);
        if(x < y) parent[y] = x;
        else parent[x] = y;
        
        weight += cost;
    }
    
    return weight - maxWeight;
}

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;

vector<pair<int, int>> graph[100001];
bool vis[100001];

int v, e;

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;
    int maxWeight = 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;
        maxWeight = max(maxWeight, cost);
        
        for(int i = 0; i < graph[cur].size(); i++) {
            pq.push({-graph[cur][i].second, graph[cur][i].first});
        }
    }
    
    return weight - maxWeight;
}

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을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐