[백준(BOJ)] 1647번 : 도시 분할 계획 - PYTHON[파이썬]

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

1647번: 도시 분할 계획

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그래프 이론
• 최소 스패닝 트리

 

---

 

⊙ 문제 접근 과정

 

문제를 보면 최소 스패닝 트리, MST 문제이다.

유지비를 최소로 길을 전부 터야 한다.

길을 입력받고 오름차순으로 정렬한다.

 

오름차순 정렬 후, 최소 스패닝 트리를 돌려준다.

부모가 다르면 값을 비교 후 작은 값이면 연결시켜 갱신, 같으면 패스한다.

 

 

---

 

⊙ 문제 풀이

 

import sys

input = sys.stdin.readline

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

for _ in range(M):
    x, y, z = map(int,input().split())
    edges.append([z,x,y])

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

def union(parent, a, b):
    rootA = find(parent,a)
    rootB = find(parent,b)

    if rootA< rootB: parent[rootB]=rootA
    else: parent[rootA]=rootB

edges.sort()
result = []

for e in edges:
    z, x, y = e

    if find(parent,x) != find(parent,y):
        union(parent,x,y)
        result.append(z)  

print(sum(result[:-1]))

 

---

⊙ 결과

 

---

 

⊙ 마무리

 

 

NONE

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!