[이것이 코딩테스트다] 어두운 길

문제

• 0번 ~ N-1 번까지의 N개의 집과 M개의 도로로 된 마을이 있다.
  • 1 <= N <= 200,000
  • N-1 <= M <= 200,000
• 모든 도로에는 가로등이 있고, 가로등을 켜기 위한 비용은 해동 도로의 길이와 동일하다.
• 일부 가로등을 비활성화해 최대한 많은 금액을 절약하려고 한다.
• 임의의 두 집이 가로등을 켜진 도로만으로도 오갈 수 있어야 한다. 

 

풀이 1

• 최소 신장 트리를 만들면 된다!
• 두 집 사이의 가로등 비용이 적은 순으로 정렬한 뒤에 하나씩 추가한다.
• 시간 복잡도 : $O(MlogM)$   => 가능!

 

import heapq

# 부모 찾기
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

# 입력 받기
N, M = map(int, input().split())
# 마을 간 도로 입력 받기
q = []  # (비용, 마을1, 마을2)
for _ in range(M):
    x, y, z = map(int, input().split())
    heapq.heappush(q, (z, x, y))    

# 비용이 적은 도로부터 하나씩 추가하기
parent = [i for i in range(N)]  # 부모 테이블
answer = 0
while q:
    cost, a, b = heapq.heappop(q)
    # 길이 없는 경우 포함해야 한다.
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
    # 길이 이미 있는 경우 절약 가능!
    else:
        answer += cost

print(answer)

 

 

 

 

 

References

• 이것이 코딩테스트다 Q43