728x90
풀이
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
728x90
'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 |