Skip to main content

1647 - 도시 분할 계획

info
  • 문제 보기: 1647 - 도시 분할 계획
  • 소요 시간: 12분 14초
  • 풀이 언어: python
  • 체감 난이도: 2️⃣~3️⃣
  • 리뷰 횟수: ✅

풀이 키워드​

스포주의

그래프 최소스패닝트리 유니온파인드


풀이 코드​

info
  • 메모리: 199932 KB
  • 시간: 3032 ms
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

parent = []

def union(a, b):
    global parent
    
    pa = find(a)
    pb = find(b)
    
    if pa < pb:
        parent[pb] = pa
    else:
        parent[pa] = pb
    
def find(x):
    global parent
    
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def solution():
    global parent
    
    n, m = map(int, input().split())
    parent = [x for x in range(n+1)]
    graph = []
    for _ in range(m):
        a, b, weight = map(int, input().split())
        graph.append((weight, a, b))
        
    path = []
    graph.sort()
    for data in graph:
        weight, a, b = data
        if find(a) != find(b):
            union(a, b)
            path.append(weight)
    
    print(sum(path) - max(path))


if __name__ == '__main__':
    solution()

풀이 해설​

path = []
graph.sort()
for data in graph:
    weight, a, b = data
    if find(a) != find(b):
        union(a, b)
        path.append(weight)

다음과 같이 크루스칼 알고리즘으로 MST를 생성하고,

print(sum(path) - max(path))

분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다.

분리된 두 마을 간에는 간선이 필요 없으므로, MST의 간선 중 가장 가중치가 큰 값을 하나 빼면 답이 된다.

마을에는 집이 하나 이상 있어야 한다.

다만 최소 하나의 집이 있어야 마을로 정의되는데,

어떤 간선을 쳐내든 분할된 마을의 형태는 모두 최소 하나의 집을 가지게 되므로, 딱히 까다로운 조건은 아니다.


메모​

  • setrecursionlimit 까먹었는데 AC받은게 ㄹㅈㄷ