[백준 1647번] 도시 분할 계획(파이썬) / 크루스칼(MST)

문제

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

1647번: 도시 분할 계획

• 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다.
  • 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다.
• 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다.
  • 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다.
  • 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다.
• 마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다.
  • 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다.
  • 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다.
  • 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다.
  • 마을에는 집이 하나 이상 있어야 한다.
• 그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다.
  • 일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다.
  • 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다.
  • 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다.
  • 이것을 구하는 프로그램을 작성하시오.

 

입력

• 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다.
• N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다.
• 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집과 B번 집을 연결하는 길의 유지비가 C (1 ≤ C ≤ 1,000)라는 뜻이다.

 

출력

• 첫째 줄에 없애고 남은 길 유지비의 합의 최솟값을 출력한다.

---

풀이

해당 문제는 최소비용으로 모든 집들을 잇는 도로들을 세운 후에 가장 비싼 비용의 도로를 하나 제거하면 된다.

즉, 최소비용 신장 트리를 구성하면 마을을 모두 잇는 MST가 세워진다.

 

이 때, MST에서 가장 비싼 비용의 도로(간선)를 하나 제거하면 두 개의 마을로 분할되고 분할된 두 마을 내에서는 모두 이어져 어디든 갈 수 있게 된다고 생각했는데 굳이 끝까지 만들 필요없이 그냥 간선의 개수를 1개 덜 만들면 된다.

 

풀이 2

최소비용으로 모든 집들을 잇는 도로(간선)들을 세우는데

 

node의 개수 -1 개의 간선일 경우 MST 인데 반해

node의 개수 - 2 개의 간선일 경우 가 정답이 된다.

 

즉, 최소비용 신장 트리를 구성하는데 한개를 덜 이을 경우 두 마을로 분할되어 모두 잇는 MST가 세워진다.

 

 

 

출처 : https://soobarkbar.tistory.com/183

import sys
input = sys.stdin.readline

# 부모 찾기
def get_parent(parent, a):
    a_parent = a
    while True:
        if parent[a_parent] == a_parent:
            return a_parent
        else:
            a_parent = parent[a_parent]

# 합치기
def union_parent(parent, a_p, b_p):
    # 그 외 index 작은 순
    if a_p < b_p:
        parent[b_p] = a_p
    else:
        parent[a_p] = b_p

# edge
class Edge:
    def __init__(self, src, dst, cost):
        self.src = src
        self.dst = dst
        self.cost = cost

    def __lt__(self, other):
        return self.cost < other.cost

# input
n, m = map(int,input().split())
parent = [i for i in range(0,n+1)]
edges= []
edge_cnt , answer = 0, 0

# main
# input 처리
for _ in range(m):
    src, dst, cost = map(int,input().split())
    edge = Edge(src,dst,cost)
    edges.append(edge)

edges.sort()

# MST 생성
for edge in edges:

    # 다채우면 종료
    if edge_cnt + 2 == n:
        break

    # 사이클 탐지
    if get_parent(parent, edge.src) == get_parent(parent, edge.dst):
        continue

    # 합치기
    union_parent(parent, get_parent(parent, edge.src), get_parent(parent, edge.dst))
    answer += edge.cost
    edge_cnt += 1

print(answer)

---

개선된 풀이

• 크루스칼을 쓰는데 heapq 를 통해 간선들의 리스트를 접근할 필요없다.
  • 어차피 cost 순으로 정렬하면 작은 것부터 하나씩 탐색해도 충분하다
  • 즉, O(logN)으로 가져갈 수 있다
• class를 따로 짤 필요 없다
  • sort를 할 때 조건을 주기 위해 짰는데 파이썬의 tuple을 활용할 경우 (a, b, c) 순이면 a 순으로 정렬 가능하다
• 파이썬 input을 개선하기 위해서 input = sys.stdin.readline을 해준다
  • 참조 : https://www.acmicpc.net/board/view/855

 

import sys
input = sys.stdin.readline

# 부모 찾기
def get_parent(parent, a):
    if parent[a] != a:
        parent[a] = get_parent(parent, parent[a])

    return parent[a]

# 합치기
def union_parent(parent, a_p, b_p):
    # index 작은 순
    if a_p < b_p:
        parent[b_p] = a_p
    else:
        parent[a_p] = b_p

# input
n, m = map(int,input().split())
parent = [i for i in range(0,n+1)]
edges= []
edge_cnt , answer = 0, 0

# main
# input 처리
for _ in range(m):
    src, dst, cost = map(int,input().split())
    edges.append((cost, src, dst))

edges.sort()

# MST 생성
for edge in edges:
    # 다채우면 종료
    if edge_cnt + 2 == n:
        break

    # 하나 꺼내기
    nc, ns, nd= edge
    # 사이클 탐지
    if get_parent(parent, ns) == get_parent(parent, nd):
        continue

    # 합치기
    union_parent(parent, get_parent(parent,ns), get_parent(parent, nd))
    answer += nc
    edge_cnt += 1

print(answer)