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

문제

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

1197번: 최소 스패닝 트리

 

 

풀이

최소 신장 트리(Minimum Spanning Tree) 자료구조

최소 신장 트리(Minimum Spanning Tree) 자료구조

 

 

코드

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;

int find_parent(int n);
void union_parent(int a, int b);
static vector<int> parent;

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

  int V, E;
  cin >> V >> E;

  vector<tuple<int, int, int>> graph;
  
  for(int i = 0; i < E; i++)
  {
    int A, B, C;
    cin >> A >> B >> C;

    graph.push_back(make_tuple(C, A, B));
  }

  sort(graph.begin(), graph.end());	// 오름차순 정렬
  reverse(graph.begin(), graph.end());

  parent.resize(V + 1);
  for(int i = 0; i <= V; i++)
  {
    parent[i] = i;  // 자기 자신의 index값으로 초기화
  }

  int count = 1;
  long result = 0;
  while(count < V)
  {
    int cost = get<0>(graph.back());
    int node1 = get<1>(graph.back());
    int node2 = get<2>(graph.back());
    graph.pop_back();

    if(find_parent(node1) != find_parent(node2))  // 같은 부모가 아니라면 ⇒ 연결해도 사이클이 생기지 않는다면
    {
      count++;  // 사용 에지 수 1 증가
      result += cost;  // 에지의 가중치를 정답 변수에 더하기
      union_parent(node1, node2);  // union_parent 연산 수행
    }
  }

  cout << result;  // 정답 변수 출력

  return 0;
}

// find_parent 연산
int find_parent(int n)
{
  if(parent[n] == n)
  {
    return n;
  }
  else
  {
    return parent[n] = find_parent(parent[n]);  // 재귀 함수 형태로 구현 ⇒ 경로 압축 부분
  }
}

// union_parent 연산 : 대표 노드끼리 연결
void union_parent(int a, int b)
{
  // a와 b의 대표 노드 찾기
  a = find_parent(a);
  b = find_parent(b);

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

 

 

오답

#include <iostream>
#include <queue>
using namespace std;

void munion(int a, int b);
int find(int a);
static vector<int> parent;

// 에지 정보 구조체 생성, 가중치 값 기준 오름차순 정렬로 설정
typedef struct Edge
{
  int s, e, v;
  bool operator > (const Edge& temp) const
  {
    return v > temp.v;
  }
} Edge;

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

  int N, M;
  cin >> N >> M;
  priority_queue<Edge, vector<Edge>, greater<Edge>> pq;  // 오름차순 정렬
  parent.resize(N + 1);

  for(int i = 0; i <= N; i++)
  {
    parent[i] = i;
  }
  for(int i = 0; i < M; i++)
  {
    int s, e, v;
    cin >> s >> e >> v;
    pq.push(Edge{s, e, v});
  }

  int useEdge = 0;
  int result = 0;

  while(useEdge < N - 1)
  {
    Edge now = pq.top();
    pq.pop();
    // 같은 부모가 아니라면 -> 연결해도 사이클이 생기지 않는다면
    if(find(now.s) != find(now.e))
    {
      munion(now.s, now.e);
      result = result + now.v;
      useEdge++;
    }
  }
  cout << result;
}

// union 연산 : 대표 노드끼리 연결
void munion(int a, int b)
{
  a = find(a);
  b = find(b);

  if(a != b)
  {
    parent[b] = a;
  }
}

// find 연산
int find(int a)
{
  if(a == parent[a])
  {
    return a;
  }
  else
  {
    // 재귀 함수 형태로 구현 -> 경로 압축 부분
    return parent[a] = find(parent[a]);
  }
}