풀이
N개의 집들에 대해 2개의 그룹으로 나누고,
M개의 길에 대해, 유지비가 최솟값이 되도록 집들을 연결해주면 된다.
단순하게 접근해보자.
Minimum Spanning Tree 문제를 풀이할 때, N개의 정점에 대해서 가중치를 기준으로 미리 정렬된 N - 1개의 간선으로 모든 정점을 연결할 수 있다는 사실을 알고있다.
그렇다면, N개의 집들을 2개의 그룹으로 나누는 가장 단순한 방법은 무엇일까?
바로, N - 2개의 간선만 이용해 N - 1개의 정점을 연결해주면 된다.
가중치에 대해 오름차순으로 정렬하고, 최소 가중치를 우선적으로 연결하는게 이득인점을 이용한 풀이다.
소스코드
출처
1647번: 도시 분할 계획
첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번
www.acmicpc.net
'PS > Baekjoon Online Judge' 카테고리의 다른 글
| [백준 18138] 리유나는 세일러복을 좋아해 [Python] (0) | 2023.06.24 |
|---|---|
| [백준 21612] Boiling Water [Python] (0) | 2023.06.22 |
| [백준 21631] Checkers [Python] (0) | 2023.06.22 |
| [백준 25192] 인사성 밝은 곰곰이 [Java] (0) | 2023.06.20 |
| [백준 2096] 내려가기 [Python] (0) | 2023.06.18 |