[백준 6497] 전력난

문제

모든 길에 가로등이 켜져있는데 어떠한 가로등을 소등하면 하루에 길의 미터 수만큼 절약할 수 있다. 하지만 어떤 두 집을 왕래할 때 불이 켜져있지 않다면 위험하다. 따라서 도시에 있는 모든 두 집 쌍에 대해 불이 켜진 길만으로 서로를 왕래할 수 있어야한다. 이 조건을 지키면서 절약할 수 있는 최대 액수를 구하시오.

 

입력

여러 개의 테스트 케이스가 주어진다.

첫째 줄에는 집의 개수 M과 길의 수 N이 주어진다. 만약 M과 N이 0이라면 더 이상의 테스트 케이스는 없다.

이어서 N개의 줄에 길에 대한 정보가 입력되고 x, y, z로 이루어진다.

x번과 y번 집 사이에 양방향 도로가 있으며 z미터라는 의미이다.

 

출력

각 테스트 케이스마다 절약할 수 있는 최대 비용을 출력한다.

---

접근

모든 두 집 쌍에 대해 불이 켜진 길만으로 왕래를 해야한다는 조건은 M개의 집이 있을 때 M-1개의 간선에 가로등을 하나씩 켜고 이 비용을 최소로 해야한다는 것이다. 따라서 연결정보가 주어졌을 때 그래프 내에서 최소 신장 트리를 구해야한다. 그리고 총 비용에서 빼주면 해를 구할 수 있다.

 

구현

- 크루스칼 알고리즘을 적용시켰다.

- 먼저 연결정보를 입력받으면서 총 비용을 total에 저장한다.

    graph = []
    home_list = [m for m in range(M)]

    total = 0
    for _ in range(N):
        x, y, z = map(int, input().split())
        total += z
        graph.append((x, y, z))

 

- 이제 비용을 기준으로 오름차순 정렬을 하고

- edge_count가 M-1개가 될 때까지 연결해야하는 간선을 찾는다.

- 간선을 찾을 때는 연결된 두 개의 집이 같은 집합에 속해있지 않을 때이며 

- 같은 집합에 속해있지 않을 때 edge_count를 1증가시키고 x와 y를 union해준다. 

- 또한 answer를 z만큼 증가시킨다.

- 최종적으로 total과 answer를 뺀 값이 해가 될 것이다.

    graph = sorted(graph, key=lambda x: x[2])

    edge_count = 0
    answer = 0
    for x, y, z in graph:
        if find_set(x) != find_set(y):
            union(x, y)
            edge_count += 1
            answer += z
        if edge_count == M-1:
            break

---

전체 코드

import sys
input = sys.stdin.readline

def find_set(a):
    if home_list[a] == a:
        return a
    else:
        b = find_set(home_list[a])
        home_list[a] = b
        return b

def union(a, b):
    a = find_set(a)
    b = find_set(b)
    if a != b:
        home_list[b] = a

while True:
    M, N = map(int, input().split())
    if M == 0 and N == 0:
        break

    graph = []
    home_list = [m for m in range(M)]

    total = 0
    for _ in range(N):
        x, y, z = map(int, input().split())
        total += z
        graph.append((x, y, z))

    graph = sorted(graph, key=lambda x: x[2])

    edge_count = 0
    answer = 0
    for x, y, z in graph:
        if find_set(x) != find_set(y):
            union(x, y)
            edge_count += 1
            answer += z
        if edge_count == M-1:
            break

    print(total - answer)