문제설명

성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들어가는데, 일부를 소등하여 그만큼의 돈을 절약할 수 있다. 그러나 만약 어떤 두 집을 왕래할 때, 불이 켜져 있지 않은 길을 반드시 지나야 한다면 위험하다. 그래서 도시에 있는 모든 두 집 쌍에 대해, 불이 켜진 길만으로 서로를 왕래할 수 있어야 한다. 위 조건을 지키면서 절약할 수 있는 최대 액수를 구하시오.

• 입력
  • 입력은 여러 개의 테스트 케이스로 구분되어 있다. 각 테스트 케이스의 첫째 줄에는 집의 수 m과 길의 수 n이 주어진다. (1 ≤ m ≤ 200000, m-1 ≤ n ≤ 200000)
  • 이어서 n개의 줄에 각 길에 대한 정보 x, y, z가 주어지는데, 이는 x번 집과 y번 집 사이에 양방향 도로가 있으며 그 거리가 z미터라는 뜻이다. (0 ≤ x, y < m, x ≠ y)
  • 도시는 항상 연결 그래프의 형태이고(즉, 어떤 두 집을 골라도 서로 왕래할 수 있는 경로가 있다), 도시상의 모든 길의 거리 합은 2^31미터보다 작다.
  • 입력의 끝에서는 첫 줄에 0이 2개 주어진다.
• 출력
  각 테스트 케이스마다 한 줄에 걸쳐 절약할 수 있는 최대 비용을 출력한다.

접근

불이 켜져 있지 않은 길을 반드시 지나야 한다면 위험하다
불이 켜진 도로만으로 이동한다는 전제로 특정 두 집 사이에 왕래가 가능해야함(경로가 존재해야 함)
절약할 수 있는 최대 액수
최소비용 신장트리를 구성해야 함

풀이

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]


def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b


while True:
    n, m = map(int, input().split())
    if n == 0 and m == 0:
        break
    edges = []
    total_cost = 0
    min_cost = 0
    parent = [0] * (n + 1)
    for i in range(1, n + 1):
        parent[i] = i

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

    edges.sort()

    for edge in edges:
        cost, a, b = edge
        if find_parent(parent, a) != find_parent(parent, b):
            union_parent(parent, a, b)
            min_cost += cost

    print(total_cost - min_cost)

배운점

크루스칼 알고리즘 내에서 사이클 판별을 서로소 집합 알고리즘의 find_parent 로 구현할 수 있다