[백준] 1647 도시 분할 계획 (python 파이썬)

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

1647번: 도시 분할 계획

---

난이도에 비해 매우 간결한 문제다. 

대신 크루스칼 알고리즘과 유니온 파인드에 대해 알고 있어야 한다.

---

아이디어

1. 마을을 두 개로 분리하는 방법

• 크루스칼 알고리즘에 대해 잘 기억하고 있다면 쉽게 떠올릴 수 있다.
• 크루스칼 알고리즘으로 최소 스패닝 트리를 만들고 여기서 비용이 가장 큰 간선을 잘라주면 된다.
• 최소 스패닝 트리에서는 사이클이 존재하지 않는다.
• 그렇기 때문에 여기서 간선 하나만 잘라주면 두 개의 스패닝 트리가 만들어진다.

---

전체 코드

import sys

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

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

N, M = map(int, input().split())

parent = [0] * (N + 1)
for i in range(1, N + 1):
    parent[i] = i


graph = []
for _ in range(M):
    graph.append([int(x) for x in sys.stdin.readline().rstrip().split()])

graph.sort(key= lambda x:x[2])

result = 0
max_cost = 0

for edge in graph:
    start, end, cost = edge
    if find_parent(start) != find_parent(end):
        union(start, end)
        result += cost
        max_cost = max(cost, max_cost)

print(result - max_cost)

---

코드 설명

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

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

유니온 파인드에 대한 내용이다.

이 부분에 대한 설명은 넘어가겠다.

 

graph.sort(key= lambda x:x[2])

result = 0
max_cost = 0

for edge in graph:
    start, end, cost = edge
    if find_parent(start) != find_parent(end):
        union(start, end)
        result += cost
        max_cost = max(cost, max_cost)

print(result - max_cost)

간선의 대한 정보를 담고 있는 그래프 리스트를 비용 순으로 정렬해준다.

그리고 각 간선을 하나씩 확인해가면서

사이클이 생기는지 안 생기는지 확인해준다.

사이클이 안 생기면 집합에 포함해주고 비용을 업데이트해준다.

 

이후 최소 스패닝 트리가 완성되면 여기서 비용이 가장 큰 간선을 지워야 하므로

미리 저장해둔 max_cost값을 빼준다.