백준 1647 도시 분할 계획 파이썬 풀이

난이도 : 골드4

풀이일 : 2401232

https://www.acmicpc.net/problem/1647

1647번: 도시 분할 계획

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

풀이 코드

import sys, heapq

# 현재 노드의 부모 탐색
def find(n):
    if parent[n] != n:
        parent[n] = find(parent[n])
    return parent[n]

# 두 노드의 부모 연결
def union(n, m):
    if n > m:
        n, m = m, n
    parent[m] = n
    return

N, M = list(map(int, sys.stdin.readline().split()))
parent = [i for i in range(N + 1)]
queue = []

for _ in range(M):
    a, b, c = list(map(int, sys.stdin.readline().split()))
    # 유지비가 작은 순서대로 저장
    heapq.heappush(queue, [c, a, b])

# 총 유지비
result = 0

# 끊을 길 유지비
last = 0

while queue:
    add, x, y = heapq.heappop(queue)
    # 두 노드의 부모가 연결되어 있지 않다면
    # 연결 후 총 유지비에 해당 길의 유지비 합산
    # 마지막 길의 정보 저장
    if find(x) != find(y):
        union(find(x), find(y))
        result += add
        last = add
        
# 전체 유지비 - 마지막 길 유지비 출력
print(result - last)

• find : 두 노드의 부모 노드 탐색
  • 만약 find 함수 반환 결과가 같다면, 두 노드의 부모가 같으므로 두 노드는 이미 연결된 상태
• union : 두 노드의 부모 노드 연결
  • 부모노드를 비교하여, 작은숫자가 부모노드가 되도록 설정 후 연결
• parent : 각 노드의 부모 노드를 담을 배열로, 처음에는 자기 자신을 담은 배열로 초기화
• 모든 주어지는 길에 대해, heapq를 사용하여 유지비용이 작은 순서대로 queue에 저장
• heapq에 들어있는 길에 대해, 두 집의 연결여부 파악
• 연결되어 있지 않다면 연결하고, 총 관리비용에 해당 도로 유지비 합산
• 마지막 길을 끊으며 유지비 차감을 위해 길의 유지비 저장
• 최종적으로 전체 연결 도로의 유지비에서 마지막 길의 유지비 차감

---

느낀점

• 아주 오래전에 배웠던 알고리즘인데, 다시 문제로 풀어보니 재미있다. 이제 여행이 시작되니까 앞으로는 이렇게는 풀 수 없겠지만 그래도 꾸준히 문제 풀 수 있도록 노력해야지.
• 트리 구조 문제들이 어렵지만 재미있게 느껴져서 몇개 모아 풀어봐야겠다.