1197 최소 스패닝 트리

BOJ::1197 최소 스패닝 트리

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

최소 스패닝 트리를 한번도 구현해본적이 없어서 블로그를 참고하여 이문제를 통해 연습해 보았다.

<프림>

#include <stdio.h>
#include <queue>
#include <utility>
#include <functional>
#define P pair<int,int>
using namespace std;
 
int prim(vector<P> *edges) {
    int ans = 0;
    //방문여부를 체크할 배열 선언
    bool visited[10001] = {false,};
    //우선순위큐 선언
    priority_queue<P, vector<P>, greater<P>> pq;
    //시작점은 1번부터
    pq.push(P(0, 1));
 
 
    while (!pq.empty()) {
        P cur = pq.top();
        pq.pop();
 
        if (visited[cur.second]) continue; //이미 방문한 지점일경우 continue
        visited[cur.second] = true;//방문하지 않았던 점인경우 방문여부 체크
 
        //비용 저장
        ans += cur.first;
 
        //방문한지 않았던 지점들에 대해서
        //우선순위 큐에 푸쉬한다.
        for (int i = 0; i < edges[cur.second].size(); i++) {
            if (!visited[edges[cur.second][i].second]) {
                pq.push(edges[cur.second][i]);
            }
        }
    }
    //비용 리턴
    return ans;
}
 
int main() {
    int V, E;
    scanf("%d %d", &V, &E);
    vector<P> edges[10001]; // 간선 정보 저장
 
    for (int i = 0; i < E; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        // edges[a].push_back(b,c) -> a-b로가는 경로의 비용 c
        edges[a].push_back(P(c, b));
        edges[b].push_back(P(c, a));
    }
 
    printf("%d \n", prim(edges));
}

<크루스칼>

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
 
struct edge {
    int u, v, c;
    edge(int u, int v, int c) {
        this->u = u;
        this->v = v;
        this->c = c;
    }
};
 
int group[10001];
 
int find(int x) {
    if (group[x] == x) return x;
    return group[x] = find(group[x]);
}
 
void merge(int x, int y) {
    x = find(x);
    y = find(y);
    group[y] = x;
}
 
int compare_edge(const edge &a, const edge &b) {
    return a.c < b.c;
}
 
int kruskal(vector<edge> &edges) {
    int ans = 0;
    sort(edges.begin(), edges.end(), compare_edge);
    for (int i = 0; i < edges.size(); i++) {
        // 사이클여부 확인
        if (find(edges[i].u) == find(edges[i].v)) continue;
        // 두 집합을 하나로 합친다.
        merge(edges[i].u, edges[i].v);
        ans += edges[i].c;
    }
    return ans;
}
 
int main() {
    int V, E;
    scanf("%d %d", &V, &E);
    vector<edge> edges;
 
    for (int i = 1; i <= V; i++) {
        group[i] = i;
    }
 
    for (int i = 0; i < E; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        edges.push_back(edge(a, b, c));
        edges.push_back(edge(b, a, c));
    }
 
    printf("%d \n", kruskal(edges));
}