[Baekjoon Online Judge] 백준 1647번 도시 분할 계획(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 1647번 도시 분할 계획

(Python)

(글쓴날 : 2020.06.16)

 

---

* Baekjoon Online Judge, 백준 1647번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 1647번 도시 분할 계획

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/1647

1647번: 도시 분할 계획

---

2) 풀이 과정

* 시간 복잡도 : O(E log E)

 

N개의 집과 유지비가 드는 M개의 길로 구성된 마을이 주어지고, 해당 마을을 길의 유지비가 최소이지만 같은 마을인 집들은 모두 연결된 두 마을로 분리할 때, 발생하는 최소 유지비를 구하는 문제입니다.

 

저의 경우, 크루스칼 알고리즘을 적용하였고, Python을 사용했습니다.

유지비가 최소가 되도록 하려면 최소 신장 트리를 구해야 하므로 주어지는 정보를 가중치인 길의 유지비에 따라 오름차순으로 정렬한 뒤, 크루스칼 알고리즘을 적용하였습니다.

그 과정 중, 유지비가 최소가 되도록 두 마을로 분리한다는 뜻은, 가장 유지비가 많이 드는 길을 끊는다는 뜻과 동치이므로, 최소 신장 트리의 총 가중치에서 마지막으로 합쳐진 길의 가중치를 제거하여 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

import sys
input = sys.stdin.readline
 
 
def find(target):
    if disjointSet[target] == target:
        return target
    
    disjointSet[target] = find(disjointSet[target])
    return disjointSet[target]
 
 
def union(sv, dv):
    findSV = find(sv)
    findDV = find(dv)
 
    if findSV == findDV:
        return False
 
    if findSV < findDV:
        disjointSet[findDV] = findSV
    else:
        disjointSet[findSV] = findDV
 
    return True
 
 
def kruskal():
    global ans
 
    count = 0
    for w, sv, dv in roads:
        if union(sv, dv):
            if count == N - 2:
                break
            
            ans += w
            
            count += 1
 
 
N, M = map(int, input().split())
 
ans = 0
disjointSet = [x for x in range(N + 1)]
 
roads = []
for _ in range(M):
    A, B, C = map(int, input().split())
 
    roads.append((C, A, B))
    roads.append((C, B, A))
 
roads.sort()
 
kruskal()
 
print(ans)

---