[백준]1647 도시 분할 계획(Python)

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

1647번: 도시 분할 계획

 

문제 접근

 

초반에 두 마을도 연결되어야 한다고 잘못 생각해서 어제 푼 최소 스패닝 트리와 같은 코드로 작성하였다.

그러면 예시의 입력값을 넣으면 12가 출력된다.

하지만 두 마을은 분리되고 하나의 마을에 최소 1개의 집이 있기에 가장 큰 길을 떼어내면 되기에 이를 담을 변수 하나만 선언하면 된다고 생각하였다. 

올바른 답인 12-4 = 8이 출력된다. 

 

예시를 직접 그려서 알고리즘을 적용해 보면,7번 집은 혼자 존재하고 나머지 4-6-1-3-2-5로 집이 연결되어 있고 비용은 1+2+2+1+2=8

 

 

코드

import sys

sys.setrecursionlimit(1000000)  # 재귀 깊이 제한 늘리기
input = sys.stdin.readline

# 찾기 연산(같은 집합에 속하는지 확인)
def find_parent(x):
    if parents[x] != x:
        parents[x] = find_parent(parents[x])
    return parents[x]


# 합집합 연산(두 집합을 합치기 위한 함수)
def union_parent(a, b):
    a = find_parent(a)
    b = find_parent(b)
    if a < b:
        parents[b] = a
    else:
        parents[a] = b

# 집(정점), 길(간선) 입력
N, M = map(int, input().split())

# 부모 테이블
parents = [i for i in range(N+1)]

# 길 정보를 담을 리스트와 최소 신장 트리 비용 변수 선언
load = []
cost = 0

for _ in range(M):
    s, e, c = map(int, input().split())
    load.append((c, s, e))

load.sort()    # 오름차순 정렬
sep = 0 # 최대 비용 담을 변수

for i in range(M):
    c, s, e = load[i]
    if find_parent(s) != find_parent(e):
        union_parent(s, e)
        cost += c
        sep = max(c, sep)

print(cost-sep)

 

문제 회고

 

sep이라는 변수에 가장 집 사이가 먼 경로를 저장하는 변수를 선언한 후 최종 cost에서 제외

생각해 보니까 굳이 max 안 해도 경로 자체가 오름차순으로 정렬되어 있기 때문에 그냥 sep = c 하는게 나을지두..