도시 분할 계획 [theory of graph] #이것이 코딩테스트다 #백준 1647

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

[문제] 도시 분할 계획: 문제 설명

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

난이도: ●●○| 풀이시간 40m | 시간제한 2초 | 메모리 256mb

 

<input case>

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

 

 

<Output case>

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

input example	Output example
7 12 1 2 3 1 3 2 3 2 1 2 5 2 3 4 4 7 3 6 5 1 5 1 6 2 6 4 1 6 5 3 4 5 3 6 7 4	8

<Idea>

Q. 최소 신장 트리라는 방식이 있던데 그걸 써야하나봐
A. 맞아 알고리즘 설계가 최소한의 거리를 사용해야하는거라 최소 신장 트리가 필요한거고 그걸 설계할때 쓰는 알고리즘이 '크루스칼 알고리즘'이었지

import sys
input = sys.stdin.readline

def find_parent(x):
    if parent[x]!=x: parent[x] = find_parent(parent[x])
    return parent[x]

def union_parent(a, b):
    a=find_parent(a)
    b=find_parent(b)
    if a==b: return
    if rank[a] < rank[b]: parent[b]=a
    elif rank[a] > rank[b]: parent[a]=b
    else:
      parent[a]=b
      rank[b]+=1

n, m = map(int, input().split())
roads= []
parent = [i for i in range(n+1)]
rank=[0]*(n+1)

for _ in range(m): roads.append(tuple(map(int,input().split())))

roads.sort(key=lambda data : data[2]) #길이를 기반으로 정렬해줍니다
result=0
cost=0
for i in roads:
    if find_parent(i[0]) != find_parent(i[1]): #두 길이 연결되어있지 않다면 이어줍시다.
        union_parent(i[0],i[1])
        result+=i[2]
        cost=i[2]

        
print(result-cost)