[BOJ / 골드 4] 도시 분할 계획

시간 제한메모리 제한제출정답맞힌 사람정답 비율

 

2 초

256 MB

19064

9831

7021

50.136%

---

문제

 

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다.

마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다.

마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다.

그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다. 일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 이것을 구하는 프로그램을 작성하시오.

 

---

입력

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

출력

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

 

 

---

예제 입력                                                                        예제 출력

7 12                                                                                     8
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

 

---

해결

 크루스칼 알고리즘만 알고 있다면 누구나 풀 수 있는 문제!!!!!!!!!!!

이것이 코딩테스트이다에서 본 것처럼 "두 도시" , "최소한의 유지비" 라는 단어만 보고 바로 크루스칼 알고리즘을 떠올릴 수 있었다.

하지만 도시를 두개로 분할하는 과정이 조금 고민되었다.

 

1.유지비가 가장 큰 애를 잘라야 하는데..... 어떻게......?

-> 최소 신장 트리를 먼저 만들고 가장 마지막에 붙은 애를 자르면 되겠다! 라는 아이디어가 떠올랐당!

 

코드

import sys
imput = 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:
        parent[b] = a
    else :
        parent[a] = b


n,m = map(int,imput().split())
parent = [0] * (n+1)

for i in range(1,n+1):
    parent[i] = i

edges = []
res = 0
#res도 필요!

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

edges.sort()

addEdges = ()
for edge in edges:
    cost,a,b = edge
    if find(parent,a) != find(parent,b) :
        union(parent,a,b)
        addEdges = (cost,a,b)
        res += cost

res -= addEdges[0]

print(res)
#사이클이 만들어지지 않는 간선 중 마지막으로 붙을 간선은 뺴야함!

 

처음 생각은 소트된 애 중 가장 뒷 부분([-1])을 뺴면 되겠구나 생각을 했었는데

그 edge가 사이클을 만들며 신장트리에 붙지 않을 수도 있겠다는 걸 꺠달았다.

그래서 addEdges를 만들어 신장트리가 만들어질 때 마다 갱신해주었고, 최종적 addEdges의 cost를 빼주면서 해결하였다. 끝!