[백준] 1647 파이썬 - 도시 분할 계획

문제

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

풀이

최소 신장 트리 문제이다.

최소 신장 트리란 가장 적은 비용 + 사이클 없음 + 모든 정점이 연결되어있는 트리이다.

 

신장 트리에서 연결된 단 하나의 간선을 끊으면 2개의 신장 트리로 나뉜다.

따라서 위 문제에서 비용이 가장 높은 간선을 끊으면 2개의 신장 트리로 나눌 수 있다.

 

나는 최소 신장 트리 구현을 위해 크루스칼 알고리즘을 사용했다.

크루스칼 알고리즘은 간선을 가중치 기준으로 정렬하고, 가중치가 작은 간선부터 선택하여 트리를 만든다.

 

자세한 풀이는 아래와 같다.

 

1. 주어진 입력을 가중치(비용 c)가 작은 순서대로 정렬

for _ in range(m):
    a,b,c = map(int,input().split())
    graph.append((c,a,b))
graph.sort()

 

2. 가중치가 작은 순서대로 트리 만들기

# 가중치가 작은 순서대로 정렬되어있는 graph
for c,a,b in graph:
    # a, b가 다른 집합에 속해있을 때
    if find(a) != find(b):
        # a, b 합치기
        union(a,b)
        # a, b가 같은 집합에 속해있는 경우는 제외된다
        answer += c
        last_edge = c

 

이때, a와 b가 이미 같은 집합에 속해있는 경우 == 반드시 가중치가 이전 트리를 그릴 때보다 크므로 가중치를 정답에 더해주지 않는다.

이미 가중치가 작은 순서대로 트리를 그려놓았기 때문이다.

 

3. 위의 과정을 거친 후 가장 마지막에 그려진 간선을 지워주면 정답이다.

가장 마지막에 그려진 last_edge == 현재 그려진 트리에서 가장 가중치가 큰 간선이므로 

answer에서 빼주면 2개의 신장 트리로 나누어진다.

 

 

코드

import sys
input = sys.stdin.readline

# 노드 n의 루트노드 return
def find(n):
    if parent[n] != n:                  
        parent[n] = find(parent[n])     
    return parent[n]                    

# a, b가 다른 집합에 속해있을 때 같은 집합으로 합치는 함수
def union(a, b):
    a = find(a)         
    b = find(b)         
    if a < b:           
        parent[b] = a   # b의 부모노드를 a로 설정
    else:               
        parent[a] = b  # a의 부모노드를 b로 설정

def solution():
    answer = 0
    graph.sort()
    # 가중치가 작은 순서대로 정렬되어있는 graph
    for c,a,b in graph:
        # a, b가 다른 집합에 속해있을 때
        if find(a) != find(b):
            # a, b 합치기
            union(a,b)
            # a, b가 같은 집합에 속해있는 경우는 제외된다
            answer += c
            last_edge = c

    return answer - last_edge # last_edge가 가중치가 가장 큰 간선이므로

n,m = map(int,input().split())
graph = []
parent = list(range(n+1))

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

print(solution())