[Python] BOJ 21924 - 도시건설

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

21924번: 도시 건설

# 그냥 문제만 읽어봐도 MST를 사용해서 푸는 문제임을 알 수 있다.

 

1. 처음에 M개의 도로를 (a, b, c)로 입력받고 build에는 (c, a, b)로 저장해준다.

    ( build.sort()를 했을때 c부터 정렬되게 하기 위해서)

 

2. total_cost에 모든 도로의 비용을 더해준 값을 넣어주고 build.sort()를 해서

   비용이 짧은 도로부터 build에 위치하도록 해준다.

 

3. Kruskal 알고리즘을 통해 비용이 낮은 도로부터 union해주며 모든 간선을 이어준다.

 

4. par[i]가 i와 같으면 tmp를 1증가시켜준다. 모든 도시가 연결되어 있다면 tmp는 1이 될 것이다.

   tmp가 2이상이면 모든 도시가 연결되어 있지 않으므로 -1을 출력하고

   tmp가 1이면 total_cost에서 cost를 빼준 절약되는 금액을 출력해준다.

 

import sys
input = sys.stdin.readline

def find(c):
	if par[c] == c:
		return c
	else:
		par[c] = find(par[c])
	return par[c]

def union(a, b):
	a, b = find(a), find(b)
	par[max(a,b)] = min(a,b)

def check(a, b):
	return find(a) == find(b)

N, M = map(int,input().split())
par = [i for i in range(N+1)]
build = []
total_cost = 0
for _ in range(M):
    a, b, c = map(int,input().split())
    build.append((c, a, b))
    total_cost += c
build.sort()

cost = 0
for c, a, b in build:
    if not check(a, b):
        cost += c
        union(a, b)

tmp = 0
for i in range(1, N+1):
    if par[i] == i:
        tmp += 1

if tmp >= 2:
    print(-1)
else:
    print(total_cost - cost)

(solved.ac 티어: 골드 4)