https://www.acmicpc.net/problem/23743
기본적인 MST 문제다.
풀이
두 가지 방법으로 풀었다. 첫 번째로 접근했던 방법은 시간이 조금 빠르지만 코드가 조금 더 길어진다.
간선의 가중치가 작은 순서로 두 정점 U, V를 연결할 때, 조건을 추가했다.
두 정점에 워프를 설치하는 비용 > 두 정점을 연결하는 간선 비용 + min( U정점에 워프 설치 비용, V정점에 워프 설치 비용)
두 정점에 탈출구 워프를 설치하는 비용이 더 저렴하다면 두 정점은 연결하지 않는다. 반대로 두 정점에 탈출구 워프 설치 비용이 더 비싸다면 간선을 연결하고 워프를 설치비용이 더 저렴한 쪽이 루트가 되어 연결하면 된다.
이후 각 컴포넌트의 루트 정점에 워프설치 비용을 더해주면 가장 작은( 간선 + 워프 설치 ) 비용이 나오는데, 마지막으로 한번 더 모든 정점에 워프 설치비용과 비교하여 더 작은 쪽을 출력하였다.
두 번째 방법은 탈출구를 0번 정점으로 취급하여 간선정보를 정렬한 뒤 MST를 수행하면 간단하게 구할 수 있다.
정답 코드-1
정답 코드 - 2
'Problem Solving > BOJ' 카테고리의 다른 글
[1765] 닭싸움 팀 정하기 (0) | 2023.10.30 |
---|---|
[23324] 어려운 모든 정점 쌍 최단 거리 (0) | 2023.10.25 |
[1833] 고속도로 설계하기 (0) | 2023.09.30 |
[16926] 배열 돌리기 1 (0) | 2023.06.15 |
[3015] 오아시스 재결합 (0) | 2023.06.12 |