[이.취.코] [백준] Chap 10. 그래프 이론 - 도시 분할 계획

@mildsalmon·2021-09-04 11:36

1. 도시 분할 계획

난이도
- 중
풀이 시간
- 40분
시간 제한
- 2초
메모리 제한
- 256MB
기출
- 기초 문제집
출처
- 1647번: 도시 분할 계획 (acmicpc.net)

A. 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.

a. 입력 조건

집의 개수 N, 길의 개수 M
- 2 <= N <= 100,000
- 1 <= M <= 1,000,000
M줄에 걸쳐 길의 정보 A, B, C가 공백으로 구분되어 주어진다.
- A번 집과 B번 집을 연결하는 길의 유지비가 C(1<=C<=1,000)이다.

c. 출력 조건

길을 없애고 남은 유지비 합의 최솟값

d. 테스트 케이스

입력 예시

출력 예시
```
8
```

B. 내 답안


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 = list(map(int, input().split()))  
array = []  
parent = [0] * (n+1)  
result = 0  
last = 0  
  
for i in range(1, n+1):  
    parent[i] = i  
  
for i in range(m):  
    a, b, c = list(map(int, input().split()))  
    array.append([c, a, b])  
  
array.sort()  
  
for i in range(m):  
    c, a, b = array[i]  
  
    if find_parent(parent, a) == find_parent(parent, b):  
        continue  
 else:  
        union_parent(parent, a, b)  
        result += c  
        last = c  
    print(parent[1:])  
  
print(result-last)  
  
# 22분 46초 / Non-Pass / 마지막 last = c를 생각 못함. (마을을 2덩어리로 나눈다고 했는데, 길 하나만 연결된 마을 2개인 줄 알았다.)