BOJ::1197 최소 스패닝 트리

[BOJ] : https://www.acmicpc.net/problem/1197

시사점

이해(x)

설계(x)

시간 복잡도

공간 복잡도

구현(프림)

// prim
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int MAX_N = 10000 + 1;

int ans;
int V, E;
bool visited[MAX_N];
vector<pair<int, int> > adj[MAX_N]; // adj[u] = {v, cost}
priority_queue<pair<int, int> > pq; // cost(min), index // pq가 전역으로 있다!!
void prim(int u){
    visited[u] = true;
    for (int i = 0; i < adj[u].size(); i++){
        int there = adj[u][i].first, cost = adj[u][i].second;
        if (visited[there] == false){
            pq.push({ -cost, there });
        }
    }
    while (!pq.empty()){
        int cost = -pq.top().first, there = pq.top().second; pq.pop();
        if (visited[there] == false){
            ans += cost;
            prim(there);
            return; // return 해 줘야한다!
        }
    }

}
int main(){
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> V >> E;
    for (int i = 0; i < E; i++){
        int x, y, c;
        cin >> x >> y >> c;
        adj[x].push_back({ y, c });
        adj[y].push_back({ x, c });
    }
    prim(1);
    cout << ans << endl;
    return 0;
}

구현(크루스칼)

// Kruscal
#include<iostream>
#include<queue>
using namespace std;
struct edge{
    int cost;
    int u;
    int v;
    bool operator <(const edge& t)const{
        return cost < t.cost;
    }
};
const int MAX_N = 10000 + 1;
int parent[MAX_N];
int find(int u){
    if (parent[u] == u) return u;
    return parent[u] = find(parent[u]);
}
void merge(int u, int v){
    u = find(u); v = find(v);
    if (u == v) return;
    parent[u] = v;
}
int V, E;
priority_queue<edge> edges; // cost(low), u, v
void Kruscal(){
    int ret = 0;
    while (!edges.empty()){
        int u = edges.top().u, v = edges.top().v, cost = -edges.top().cost; edges.pop();
        if (find(u) == find(v)) continue;
        merge(u, v);
        ret += cost;
    }
    cout << ret << endl;
}
int main(){
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> V >> E;
    for (int i = 0; i < E; i++){
        int x, y, c;
        cin >> x >> y >> c;
        edges.push({ -c, x, y });
    }
    for (int i = 0; i < V; i++)
        parent[i] = i;
    Kruscal();
    return 0;
}

디버깅(x)

좋은 코드

최적화