백준 1197번 - 최소 스패닝 트리

www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

알고리즘 기말 공부를 하다가 갑자기 꽂혀서 풀어보았어요..

 

분명 구글에 red-black-tree의 유일성을 찾아보고 있었는데 뭐지..?

 

어쨌든 최소 스패닝 트리는 두 가지 방법으로 구할 수 있다.

 

1. 프림 알고리즘
2. 크루스칼 알고리즘

둘 다 이산수학, 자료구조 시간에 배운 알고리즘인데 거의? 비슷하다.

나는 프림 알고리즘으로 풀었으니까 프림 알고리즘에 대해 설명해보자면

 

1. 시작 노드 선택 (스패닝 트리의 루트가 되겠죠)

2. 선택된 노드들(즉 스패닝 트리)와 연결된 간선 중 가중치가 가장 적은 간선을 연결한다.

 (이 때 priority queue를 사용할 거고, 한번 방문한 노드는 방문하지 않는다)

3. 모든 노드를 방문할 때까지 2번 반복

 

코드에 자세하게 주석 달아놨습니다. 

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
 
vector<pair<int,int>> g[10004];
bool check[10004];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    memset(check, false, sizeof(check));
    int v, e, a, b, c;
    int ans = 0;
    cin >> v >> e;
    for (int i = 0; i < e; i++) {
        cin >> a >> b >> c;
        g[a].push_back(make_pair(b, c));
        g[b].push_back(make_pair(a, c));
    }
    // prim 알고리즘을 통해 구해보자
    // 1. 1번 정점을 스패닝 트리의 루트라고 가정
    int start = 1;
    // 2. 우선순위 큐를 통해 트리와 연결된 간선 중 가중치가 가장 작은 간선을 찾아서 트리로 연결한다
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> pq;
    pq.push(make_pair(0, start));
    while (!pq.empty()) {
        int ver = pq.top().second;
        int edge = pq.top().first;
        pq.pop();
        // 이미 방문한 정점이라면 건너뛴다.
        if (check[ver]) continue;
        // 방문하지 않은 정점이라면 해당 정점과 연결된 모든 정점을 pq에 (간선, 정점) 으로 넣어준다
        check[ver] = true;
        // pq에 들어가는 정점들은 모두 현재 만들어진 트리에서 방문할 수 있는 정점들이다.
        for (int i = 0; i < g[ver].size(); i++) {
            pair <int, int> nx = g[ver][i];
            if (check[nx.first] == false) pq.push(make_pair(nx.second, nx.first));
        }
        // 답에 가중치를 더해준다.
        ans += edge;
    }
    cout << ans << "\n";
}

 

추가적으로 백준 1922번 - 네트워크 연결 문제도 위와 똑같은 코드로 Accept 받음!

(똑같은 코드여서 안쓰려고 했는데 400문제가 딱 저 녀석이어서ㅎㅎ)

www.acmicpc.net/problem/1922

1922번: 네트워크 연결