https://www.acmicpc.net/problem/13905
13905번: 세부
첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄
www.acmicpc.net
최소 스패닝 트리 문제다. 단 여기서 간선의 비용이 최대가 되게 구하면 된다. 주의할 점은 숭이가 위치한 곳과 혜빈이가 위치한 곳이 다리로 연결된다는 보장이 없다는 것을 숙지하고 풀어야 한다. 이것 때문에 오답 판정을 받았다.
풀이
입력되는 간선의 가중치, 즉 무게가 높은 순으로 간선의 정보를 정렬한 뒤, 가중치가 높은 순서로 유니온을 수행한다. 유니온을 수행할 때마다 들고 갈 수 있는 빼빼로의 무게를 작은 값으로 갱신, 마지막으로 숭이와 혜빈이의 위치가 같은 컴포넌트에 속해있는지 확인한 후, 같은 컴포넌트가 아니라면, 빼빼로를 전달할 수 없는 것이므로 0을 출력, 같은 컴포넌트가 맞다면 갱신해온 무게 값을 출력하면 된다.
정답 코드
'Problem Solving > BOJ' 카테고리의 다른 글
| [14594] 동방 프로젝트 (Small) (0) | 2022.12.18 |
|---|---|
| [16168] 퍼레이드 (0) | 2022.12.16 |
| [16724] 피리 부는 사나이 (0) | 2022.12.13 |
| [20955] 민서의 응급 수술 (0) | 2022.12.12 |
| [10216] Count Circle Groups (0) | 2022.12.11 |