[BOJ/Python] 21924_도시 건설

문제 출처:https://www.acmicpc.net/problem/21924

 

문제

채완이는 신도시에 건물 사이를 잇는 양방향 도로를 만들려는 공사 계획을 세웠다.

공사 계획을 검토하면서 비용이 생각보다 많이 드는 것을 확인했다.

채완이는 공사하는 데 드는 비용을 아끼려고 한다. 

모든 건물이 도로를 통해 연결되도록 최소한의 도로를 만들려고 한다.

위 그림에서 건물과 직선으로 표시된 도로, 해당 도로를 만들 때 드는 비용을 표시해놓은 지도이다.

그림에 있는 도로를 다 설치할 때 드는 비용은 62이다. 모든 건물을 연결하는 도로만 만드는 비용은 27로 절약하는 비용은 35이다.

채완이는 도로가 너무 많아 절약되는 금액을 계산하는 데 어려움을 겪고 있다.

채완이를 대신해 얼마나 절약이 되는지 계산해주자.

입력

출력

예산을 얼마나 절약 할 수 있는지 출력한다. 만약 모든 건물이 연결되어 있지 않는다면 -1을 출력한다.

예제 입력 1

7 9
1 2 15
2 3 7
1 3 3
1 4 8
3 5 6
4 5 4
4 6 12
5 7 1
6 7 6

예제 출력 1

35

예제 입력 2

8 10
1 2 4
2 3 9
2 4 9
3 4 4
3 5 1
4 6 14
6 7 5
5 7 3
7 8 7
6 8 3

예제 출력 2

30

예제 입력 3

5 4
1 2 1
2 3 1
3 1 1
4 5 5

예제 출력 3

-1

 

 

---

풀이

 

모든 건물들이 도로를 통해 연결되도록 하여야 한다.

여기서 도로의 비용의 합이 최소가 되도록 하여야 하므로, 최소 신장 트리를 구하는 문제임을 알 수 있다.

 

이 문제에서는 만들어진 도로의 비용의 합을 구하는 것이 아닌 얼마만큼 절약하였는지를 구하는 문제이므로, 연결되지 않은 도로의 비용의 합을 구하여 출력하면 된다.

 

코드는 다음과 같다.

 

import sys
 
def find_parent(parent,x):
    if parent[x]!=x:
        parent[x] = find_parent(parent,parent[x])
    return parent[x]
 
def union_parent(parent,a,b):
    a = find_parent(parent,a)
    b = find_parent(parent,b)
 
    if a<b:
        parent[b] = a
    else:
        parent[a] = b
 
 
n,m = map(int,sys.stdin.readline().split())
 
parent = [i for i in range(n+1)]
edges=[]
 
for _ in range(m):
    edges.append(tuple(map(int,sys.stdin.readline().split())))
 
edges.sort(key=lambda x:x[2])
 
l = 0
result = 0
for a,b,c in edges:
    if l==n-1:
        result+=c
    else:
        if find_parent(parent,a)!=find_parent(parent,b):
            union_parent(parent,a,b)
            l+=1
        else:
            result+=c
 
if l<n-1:
    result = -1
 
print(result)

 

• 두 건물과 연결되어 있는 도로의 정보를 입력받아 (도시 1, 도시 2, 도로의 비용)의 튜플 형태로 만들어 edges 리스트에 추가한다.
• edges 리스트를 도로의 비용을 기준으로 오름차순으로 정렬한다.
• 만약 n-1개의 간선이 연결되었다면 최소 신장 트리가 완성되었으므로, 이후에 나오는 간선들은 연결되지 않는 간선들이므로 result에 해당 도로의 비용을 더해준다.
• 아직 최소 신장 트리가 완성되지 않은 경우라면, 두 도로가 같은 집합인지 확인한다.
• 같은 집합이 아니라면 union_parent 함수를 이용하여 하나의 집합으로 합친다.
• 만약 같은 집합이라면 도로를 추가로 연결하게 되면 사이클이 생기므로 최소 비용이 아니게 되므로, 도로를 연결하지 않는다. 따라서 이 도로는 사용하지 않으므로 result에 현재 도로의 비용을 더해준다.
• 최종적으로 간선들을 다 살펴봤을 때, 연결된 간선의 개수가 n-1개 보다 작다면 연결되지 않은 건물이 존재한다는 뜻이므로 result를 -1로 바꾼다.
• result를 출력한다.