BOJ 1197

19 May 2020 • ProblemSolving

최소 스패닝 트리

문제출처

문제 해석

최소 스패닝 트리의 가중치를 출력하는 문제입니다.

설계(X)

MST 알고리즘을 파악하기 위해서 crocus님의 블로그를 참조하였습니다.(항상 잘 정리해주시는 crocus님께 감사드립니다)

우선 MST는 두가지 방법으로 해결할 수 있습니다.

  1. Kruskal 알고리즘

    • Greedy한 방법으로 가중치가 최소인 간선을 하나씩 이어가는 방법입니다.

    • 우선, 가중치를 기준으로 오름차순 정렬을 합니다.

    • 그리고 Union-Find알고리즘을 이용하여 사이클여부를 체크한 후, 연결합니다.

    • 총 시간복잡도는 정렬에 의해 좌우되므로 O(ElogE)가 됩니다.

  2. Prim 알고리즘

    • 정점을 기준으로 최소 가중치를 가지는 간선을 하나씩 연결하는 방법입니다.

    • 우선순위큐에 해당 정점에서 이동가능한 간선을 모두 저장합니다.

    • 우선순위큐는 가중치가 적은 것을 우선순위로 둡니다.

    • 방문표시를 함으로써 사이클을 만들지 않도록 합니다.

    • 총 시간복잡도는 정점을 우선순위큐에 담고, 해당 정점을 모두 탐색해야하므로 O(ElogV)가 됩니다.

구현 (X)

코드 1 (Kruskal)
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAXN 10001

int parent[MAXN];

struct node{
    int u,v,w;
    bool operator <(const node& a)const{
        return w < a.w;
    }
};
vector<node> adj;
int V,E;
int Find(int x){
    if (parent[x]==-1) return x;
    return parent[x] = Find(parent[x]);
}
bool Merge(int u, int v){
    u = Find(u);
    v = Find(v);
    if (u==v) return false;
    parent[u] = v;
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(parent,-1,sizeof(parent));
    cin >> V >> E;
    for (int i = 0 ;i <E; i++){
        int u,v,w;
        cin >> u >> v >> w;
        adj.push_back({u,v,w});
    }
    sort(adj.begin(),adj.end());
    int ans = 0;
    for (int i = 0 ;i < adj.size(); i++){
        if (Merge(adj[i].u,adj[i].v)) ans+=adj[i].w;
    }
    cout << ans <<"\n";
    return 0;

}
코드 2 (Prim)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define MAXN 10001


vector<pair<int,int> > adj[MAXN];
bool visited[MAXN];
priority_queue<pair<int,int> > pq;
int V,E;
int ans;
void go(){
    visited[1] = true;
    for (int i = 0 ;i < adj[1].size(); i++){
        int next = adj[1][i].first;
        int next_w = adj[1][i].second;
        pq.push({-next_w,next});
    }
    while (!pq.empty()){
        int cur = pq.top().second;
        int cur_w = -pq.top().first;
        pq.pop();
        if (visited[cur]) continue;
        visited[cur] = true;
        ans += cur_w;
        for (int i = 0 ;i < adj[cur].size(); i++){
            int next = adj[cur][i].first;
            int next_w = adj[cur][i].second;
            pq.push({-next_w,next});
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> V >> E;
    for (int i = 0 ;i <E; i++){
        int u,v,w;
        cin >> u >> v >> w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    go();
    cout << ans <<"\n";
    return 0;

}
디버깅
제출결과

코드1 : 36 ms 코드2 : 68 ms

마무리

MST를 구현하는 문제였습니다.

각 MST 알고리즘을 연습하기에 아주 적당한 문제인 것 같습니다.

 BOJ

Related Posts