[백준/C++] 1197번. 최소 스패닝 트리

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

1. 문제

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

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

2. 입력

첫째 줄에 정점의 개수 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보다 작거나 같은 데이터만 입력으로 주어진다.

3. 출력

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

4. 풀이

• 최소 신장 트리 문제
• 간선에 연결된 두 노드와 간선의 비용을 배열에 입력한다.
• 비용 순으로 배열을 정렬한다.
  비용이 적은 간선을 먼저 처리해야 최소 비용으로 연결할 수 있다.
• 배열에서 순서대로 꺼내면서 사이클이 발생하는지 확인한다.
  사이클 발생 = 불필요한 간선
사이클 발생 확인법 = 각 노드의 부모가 같은 지 확인한다.

5. 처음 코드와 달라진 점

• 배열을 정렬해주지 않아서 수정했다.

6. 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int v, e;
int parent[10001];
vector<pair<int, pair<int, int> > > graph;

int findParent(int x) {
  if(x == parent[x]) return x;
  else return findParent(parent[x]);
}

void unionParent(int a, int b) {
  a = findParent(a);
  b = findParent(b);

  if (a < b) parent[b] = a;
  else parent[a] = b;
}

int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);

  cin>>v>>e;

  for (int i = 1; i <= v; i++) {
    parent[i] = i;
  }
  
  for (int i = 0; i < e; i++) {
    int a, b, cost;
    cin>>a>>b>>cost;

    graph.push_back({cost, {a, b}});
  }

  sort(graph.begin(), graph.end());
  
  int totalCost = 0;
  for (int i = 0; i < graph.size(); i++) {
    int cost = graph[i].first;
    int a = graph[i].second.first;
    int b = graph[i].second.second;

    if (findParent(a) != findParent(b)) {
      totalCost += cost;
      unionParent(a, b);
    }
  }
  
  cout<<totalCost;
}