알고리즘 스터디 - 백준 6497번 : 전력난

문제 해석

1. 비용 = 길이 m
2. 왕래 과정에서 불이 켜진 곳만 지나갈 수 있음
3. 1 <= m-1 <= m <= n <= 200000
4. 첫째 줄은 m, n
5. 두번째 줄은 x, y, z인데 [x번 집, y번 집, z길이]
6. 모든 길의 합은 2^31
7. 0 0 이 2개면 입력이 끝남

이 문제는 도로 길이나 전선 길이를 나타내는 것으로 최소신장길이를 구하는 MST 알고리즘을 이용하면 된다. 크루스칼 알고리즘만 그냥 이용해도 문제가 바로 풀리는 것이다. 크루스칼 알고리즘 참고하기

코드 해석

# 특정 원소가 속한 집합 찾기
def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]
    
# 두 원소가 속한 집합 찾기
def union(parent, a, b):
    rootA = find(parent, a)
    rootB = find(parent, b)

    if rootA < rootB:
        parent[rootB] = rootA
    else:
        parent[rootA] = rootB

while True:
    # 노드의 개수와 간선의 개수 입력받기
    m, n = map(int, input().split())
    if m == 0 and n == 0:
        break
    parent = [0] * (m+1)

    edges = []
    result = 0

    # 부모 테이블 상에서, 부모를 자기 자신으로 초기화
    for i in range(1, m + 1):
        parent[i] = i

    # 모든 간선에 대한 정보를 입력받기
    for _ in range(n):
        a, b, cost = map(int, input().split())
        edges.append((cost, a, b))

    edges.sort()

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