[Python] 백준 1647 도시 분할 계획 | 크루스칼 알고리즘

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

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

1647번: 도시 분할 계획

 

 

문제 해결 포인트

- 최소 스패닝 트리 문제 (크루스칼 알고리즘)

- edges : 간선 비용을 오름차순으로 저장할 리스트

- parent : 서로소 집합 정보 저장할 리스트

- find_parent(x) : 서로 같은 집합에 속해있는지 확인하는 함수

- union_parent(a, b) : a, b 정점에 대해 같은 집합에 속하도록 parent 수정

 

-오름차순 정렬된 edges를 하나씩 방문하며 사이클이 발생하지 않는다면( find(a) != find(b) ) 연결

- 오름차순에서 마지막으로 연결된 간선 비용(last)을 모든 연결된 간선 비용에서 빼면 결과

 

 

작성 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
edges = []
parent = [i for i in range(N+1)]

def find_parent(x):
    if parent[x] != x:
        parent[x] = find_parent(parent[x])
    return parent[x]

def union_parent(a, b):
    a = find_parent(a)
    b = find_parent(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

for _ in range(M):
    a, b, c = map(int, input().split())
    edges.append((c, a, b))

edges.sort()
result = 0
last = 0
for w, a, b in edges:
    if find_parent(a) != find_parent(b):
        union_parent(a, b)
        result += w
        last = w

print(result-last)

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚