217. 어두운 길

• 마을은 N개의 집과 M개의 도로로 구성되며, 각 집은 0번부터 N - 1번까지의 번호로 구분된다.

• 도로에 가로등을 하루 동안 켜기 위한 비용은 해당 도로의 길이와 동일하다.

• 일부 가로등을 비활서와하되, 마을에 있는 임의의 두 집에 대하여 가로등이 켜진 도로만으로도 오갈 수 있도록 만들고자 한다.

  • 일부 가로등을 비활성화하여 절약할 수 있는 최대 금액을 출력하는 프로그램을 작성하시오.

• 입력조건

  • 첫째 줄에 집의 수 N(1 ≤ N ≤ 200,000)과 도로의 수 M(N-1 ≤ M ≤ 200,000)이 주어집니다.

  • 다음 M개의 줄에 걸쳐서 각 도로에 대한 정보 X, Y, Z가 주어지며, 공백으로 구분합니다. (0 ≤ X, Y < N)

    • 이는 X번 집과 Y번 집 사이에 양방향 도로가 있으며, 그 길이는 Z라는 의미입니다.

    • 단, X와 Y가 동일한 경우는 없으며 마을을 구성하는 모든 도로의 길이의 합은 2³¹보다 작습니다.

• 출력조건

  • 첫째 줄에 일부 가로등을 비활성화하여 절약할 수 있는 최대 금액을 출력합니다.

크루스칼 알고리즘

🛑 '임의의 두 집에 대하여 가로등이 켜진 도로만으로도 오갈 수 있도록'과 같은 문장이 있으면, 최소 신장 트리 문제라는 것을 의심해야 한다.

• '왕래'할 수 있다는 것은 그래프에서 각 노드가 서로 연결되어 있다는 의미(연결 그래프)와 같기 때문이다.

import sys
input = sys.stdin.readline

def find(x):
  if parent[x] == x:
    return x
  parent[x] = find(parent[x])
  return parent[x]

def union(a, b):
  a = find(a)
  b = find(b)
  if a != b:
    parent[b] = a

n, m = map(int,input().split())
parent = [0] * (n)
edges = []
result = 0

for i in range(n):
  parent[i] = i

for _ in range(m):
  a, b, c = map(int, input().split())
  edges.append((c, a, b))

edges.sort()
total = 0 #전체 가로등 비용

for edge in edges:
  cost, a, b = edge
  total += cost
  if find(a) != find(b):
    union(a, b)
    result += cost

print(total - result)
print(parent)

2. C++

#include <bits/stdc++.h>

using namespace std;

// 노드의 개수와 간선의 개수
int n, m;
int parent[200001]; // 부모 테이블 초기화
// 모든 간선을 담을 리스트와, 최종 비용을 담을 변수
vector<pair<int, pair<int, int> > > edges;
int result;

// 특정 원소가 속한 집합을 찾기
int findParent(int x) {
    // 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if (x == parent[x]) return x;
    return parent[x] = 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(void) {
    cin >> n >> m;

    // 부모 테이블상에서, 부모를 자기 자신으로 초기화
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }

    // 모든 간선에 대한 정보를 입력받기
    for (int i = 0; i < m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        // 비용순으로 정렬하기 위해서 튜플의 첫 번째 원소를 비용으로 설정
        edges.push_back({z, {x, y}});
    }

    // 간선을 비용순으로 정렬
    sort(edges.begin(), edges.end());
    int total = 0; // 전체 가로등 비용

    // 간선을 하나씩 확인하며
    for (int i = 0; i < edges.size(); i++) {
        int cost = edges[i].first;
        int a = edges[i].second.first;
        int b = edges[i].second.second;
        total += cost;
        // 사이클이 발생하지 않는 경우에만 집합에 포함
        if (findParent(a) != findParent(b)) {
            unionParent(a, b);
            result += cost;
        }
    }

    cout << total - result << '\n';
}