[백준] 1197번 최소 스패닝 트리 c++

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

1197번: 최소 스패닝 트리

 

문제

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

 

문제접근 및 풀이

- 최소 스패닝 트리 알고리즘의 개념을 연습할 수 있는 문제다.

- prim 알고리즘을 사용했다. (union find을 사용하는 크루스칼 알고리즘도 있다.)

 

프림 알고리즘

- 노드 중심으로 탐색한다. 
- priority_queue를 사용하여 가장 작는 가중치는 갖는 연결된 간선을 선택한다. 
- 이때 이미 방문한 노드면 pass한다 -> 방문한 노드만 아니면 싸이클이 무조건 안 생긴다.

- 방문하지 않은 노드에 한해서 해당 노드와 연결된 모든 간선을 priority_queue에 넣는다.
- pq가 빌때까지 진행한다. -> 이미 방문한 정점들이면 알아서 다 빠지기 때문이다.

#include <iostream>
#include <vector>
#include <queue>
#define VMAX 10001

using namespace std;

vector<pair<int,int>> a[VMAX];

int solve(){
  int result=0;;
  int v[VMAX]={0};
  priority_queue<pair<int,int>> pq; // priority_queue를 사용하여 연결된 간선중 가장 작은 가중치를 갖는 값을 우선적으로 탐색한다.
  pq.push({-0, 1}); // 어디서 시작하는지 관계없으므로 임의로 1번 정점에서 시작한다.
  //이때 1번 노드는 방문처리 하지 않는다. 1번 노드로 시작하는 것이지 탐색을 진행한게 아니기 때문이다.
  while(!pq.empty()){
    int x = pq.top().second;
    int w = -pq.top().first;
    pq.pop();
    if(v[x]==1) continue; // 이미 방문한 정점이면 pass

    result+=w; // 가중치 ++ 
    v[x]=1; // 방문체크
    for(int i=0; i<a[x].size(); i++){ // 방문한 노드에 연결된 모든 간선을 pq에 추가한다.
      int y = a[x][i].first;
      int wy = a[x][i].second;
      pq.push({-wy,y});
    }
  }

  return result;
}

int main(){
  int n,e; cin >> n >> e;
  for(int x,y,w,i=0; i<e; i++){
    scanf("%d %d %d", &x, &y ,&w);
    a[x].push_back({y,w});
    a[y].push_back({x,w});
  }
  cout << solve();
  return 0;
}

 

느낀점

- 최소스패닝 트리 알고리즘에 정답을 보지 않고 충분히 생각해 본 후에 프림알고리즘을 접하니 훨씬 이해가 쉬웠고 왜 알고리즘을 이렇게 짜여져야 하는지 쉽게 납득이 되고 채화시킬 수 있었다.