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

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

1647번: 도시 분할 계획

오늘 백준을 들어가보니 AC Rating이 갑자기 50정도 늘어나있었다.

아무 문제도 푼게 없는데 무슨 일인가 싶다...ㅋㅋㅋ

얼떨떨한 기분으로 푼 문제, '도시분할계획'이다.

 

이 문제는 MST 응용문제인데, 두 MST의 합을 최소로 해야한다는 점이 조금 까다롭게 느껴졌다.

처음에는 두 MST에 속할 노드를 백트레킹이나 조합으로 골라서 매번 MST를 구해야하나 싶었으나

아무리봐도 이건 구현난이도도 어렵고 시간도 부족할 것 같아보였다.

 

그래서 노트에 생각을 정리하다보니 아이디어가 금방 떠올랐다.

DP 알고리즘의 전깃줄 문제처럼 발상의 전환을 하면된다.

전체 노드의 MST를 구하고, 해당 MST의 구성 간선중 제일 가중치가 큰 간선을 제거하면

MST가 2개의 연결요소로 나누어지는데, 각 연결요소 역시 MST이므로 구하는 답의 조건을 만족한다.

 

import sys
input = sys.stdin.readline

def find(node):
    if parent[node] == node:
        return node
    parent[node] = find(parent[node])
    return parent[node]

def union(node1, node2):
    node1 = find(node1)
    node2 = find(node2)
    parent[node2] = node1

n, m = map(int, input().split())
edges = []
parent = [i for i in range(n+1)]
for _ in range(m):
    edges.append(tuple(map(int, input().split())))
edges.sort(key=lambda x: -x[2])
edge_count, answer = 0, 0
while edges:
    house1, house2, cost = edges.pop()
    if find(house1) == find(house2):
        continue
    union(house1, house2)
    answer += cost
    edge_count += 1

    if edge_count == n - 1:
        answer -= cost
        break

print(answer)

나는 가장 작은 가중치의 간선을 고를때, 그냥 리스트에 역순으로 간선을 정렬해서 넣고, pop() 메소드를 썼다.

pop 메소드는 맨 앞의 요소를 꺼낼땐 O(n)의 시간복잡도를 갖지만, 맨 뒤의 요소를 꺼낼땐 O(1)의 시간복잡도를 갖는다.