Chap 18. 그래프이론 - Q43. 어두운 길

@mildsalmon·2021-12-01 10:04

1. 어두운 길

난이도
- 중
풀이 시간
- 40분
시간 제한
- 1초
메모리 제한
- 128MB
출처
- University of Ulm Local Contest

A. 📜 문제

한 마을은 N개의 집과 M개의 도로로 구성되어 있다. 각 집은 0번부터 N-1번까지의 번호로 구분된다. 모든 도로에는 가로등이 구비되어 있는데, 특정한 도로의 가로등을 하루 동안 켜기 위한 비용은 해당 도로의 길이와 동일하다.

정부에서 일부 가로등을 비활성화하되, 마을에 있는 임의의 두 집에 대하여 가로등이 켜진 도로만으로도 오갈 수 있도록 만들고자 한다. 결과적으로 일부 가로등을 비활성화하여 최대한 많은 금액을 절약하고자 한다. 마을의 집과 도로 정보가 주어졌을 때, 일부 가로등을 비활성화하여 절약할 수 있는 최대 금액을 출력하는 프로그램을 작성하라.

a. 예를 들면.

예를 들어 2번 집과 3번 집 사이를 연결하는 길이가 7인 도로가 있다고 하면, 하루 동안 이 가로등을 켜기 위한 비용은 7이다.

b. 입력 조건

첫째 줄에 집의 수 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^31$보다 작다.

c. 출력 조건

첫째 줄에 일부 가로등을 비활서오하하여 절약할 수 있는 최대 금액을 출력하라.

d. 테스트 케이스

입력 예시

출력 예시
```
51
```

B. 💡 내 답안

a. 😊 1차 시도 (성공)


"""
Date    : 2021.12.01
Update  : 2021.12.01
Source  : Q43_어두운 길.py
Purpose : 크루스칼 알고리즘 적용하여 해결.
Author  : 김학진 (mildsalmon)
Email   : mildsalmon@gamil.com
"""
# 각 집 사이의 거리가 최소인 길만 가로등을 켠다. -> 크루스칼 알고리즘
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[a] = b
    elif a < b:
        parent[b] = a

n, m = list(map(int, input().split()))

roots = []
# 집의 번호가 0 ~ N-1번으로 주어졌기 때문에 parent의 원소 갯수를 n개만 생성함.
parent = [0] * n
save_cost = 0

for _ in range(m):
    x, y, z = list(map(int, input().split()))
    # 크루스칼 알고리즘을 사용하기 위해(비용 순으로 정렬하기 위해), 길에 대한 정보를 바꿔서 roots 리스트에 집어넣음.
    roots.append((z, x, y))
# 최소 비용의 길부터 탐색하기 위해 첫번째 원소를 기준으로 정렬을 함.
roots.sort()

# 초기 각 집의 부모를 자기 자신으로 초기화함.
for i in range(1, n):
    parent[i] = i

for root in roots:
    cost, a, b = root
    # 부모가 같지 않다면(싸이클이 없다면) union 연산을 함.
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
    else:
        # 문제에서 구하고자 하는 값이 가로등을 비활성하여 절약할 수 있는 금액임.
        # 따라서 가로등을 켜지 않는 경우를 누적하여 합함.
        save_cost += cost

print(save_cost)