문제
백준 6497번-전력난(https://www.acmicpc.net/problem/6497)
문제설명
성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들어가는데, 일부를 소등하여 그만큼의 돈을 절약할 수 있다.
그러나 만약 어떤 두 집을 왕래할 때, 불이 켜져 있지 않은 길을 반드시 지나야 한다면 위험하다. 그래서 도시에 있는 모든 두 집 쌍에 대해, 불이 켜진 길만으로 서로를 왕래할 수 있어야 한다.
위 조건을 지키면서 절약할 수 있는 최대 액수를 구하시오.
입력
입력은 여러 개의 테스트 케이스로 구분되어 있다.
각 테스트 케이스의 첫째 줄에는 집의 수 m과 길의 수 n이 주어진다. (1 ≤ m ≤ 200000, m-1 ≤ n ≤ 200000)
이어서 n개의 줄에 각 길에 대한 정보 x, y, z가 주어지는데, 이는 x번 집과 y번 집 사이에 양방향 도로가 있으며 그 거리가 z미터라는 뜻이다. (0 ≤ x, y < m, x ≠ y)
도시는 항상 연결 그래프의 형태이고(즉, 어떤 두 집을 골라도 서로 왕래할 수 있는 경로가 있다), 도시상의 모든 길의 거리 합은 231미터보다 작다.
입력의 끝에서는 첫 줄에 0이 2개 주어진다.
출력
각 테스트 케이스마다 한 줄에 걸쳐 절약할 수 있는 최대 비용을 출력한다.
주요 포인트
-
도시에 있는 모든 두 집 쌍에 대해, 불이 켜진 길만으로 서로를 왕래할 수 있어야 한다. => 모든 집이 서로 연결되어 있는 것이 아니라면, 불이 꺼진 길로 왕래해야 할 일이 생길 수 있기 때문에, 도시의 모든 집은 서로 연결되어야 합니다. 또한, 최대로 절약해야 하니 연결된 간선의 개수도 최소인(n-1)개여야 합니다.
-
간선들마다 가중치(돈)이 정해져 있는 무방향 그래프가 주어집니다. 절약할 수 있는 최대 액수를 구하는 문제이기 때문에, 길을 왕래함에 있어 같은 길을 다시 반복해서 가는 일은 없어야 합니다. => 반복이 없어야 하기 때문에, 서로 다른 두 도시를 연결하는 길이 하나뿐이므로, 트리구조가 됩니다.
-
1번 조건에 부합하며, 간선간의 반복(사이클)이 없고, 최소 비용을 구해야 하므로 최소 신장 트리(MST)를 이용합니다. => 위 조건에 모두 부합하는 최소신장트리를 만들기 위해 크루스칼 알고리즘을 이용합니다.
-
절약할 수 있는 최대 액수가 문제에서 원하는 답이므로, (전체 액수 - 이어진 도시의 가중치 합)을 구해주면 됩니다. => 반대로 말하면 연결되지 않는 경우의 값만 알면 되는 것이므로, 그 값을 구해줘도 됩니다.
코드
import sys
input = sys.stdin.readline
#유니온 파인드 알고리즘을 통해 부모 노드를 통일
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
x, y = find(x), find(y)
if x < y:
parent[y] = x
else:
parent[x] = y
while True:
m, n = map(int, input().split())
if m == 0 and n == 0: #0이 2개 주어질 경우 종료합니다.
break
parent = [i for i in range(m)]
cost = 0
# edges = [list(map(int, input().strip().split())) for _ in range(n)] 아래와 같은 동작을 수행합니다.
edges = []
for _ in range(n):
u, v, w = map(int, input().split()) #출발점, 도착점, 간선의 가중치
edges.append((u, v, w))
edges.sort(key=lambda x: x[2]) #가중치를 중심으로 오름차순으로 정렬해줍니다.
for edge in edges:
u, v, w = edge
if find(u) != find(v): #유니온 파인드로 부모 노드가 같은지 보고, 아니라면 통일해줍니다.
union(u, v)
else: #문제에서 원하는 것이 절약되는 액수이므로, 연결되지 않은 간선의 가중치를 더해줍니다.
cost += w
print(cost)
생각🤔
최소신장트리(MST)를 알고, MST를 만드는 알고리즘(크루스칼, 프림)을 알고 있었다면 무리없이 풀 수 있었을 문제라는 생각이 들었습니다.
마지막 코드를 저렇게 작성한 이유는, 보편적으로는 MST의 가중치 합을 총 액수에서 빼주겠지만, 반대로 MST를 만드는 간선 이외의 것만 더하면 그것 자체가 답이 될 것이라 생각하여 저렇게 풀었습니다.
