목록13905 (1)

그거 기능이에요

백준 13905 세부

문제 설명섬과 다리들이 있는 세부에서 숭이는 혜빈이의 위치까지 가려고 한다.각 다리마다 무게제한이 있는데 숭이는 혜빈이까지 최대 얼마의 무게를 지니고 도착할 수 있는지 구하여라문제 링크문제 접근a에서 b까지의 최소한의 간선을 지나는 것이므로 최소 스패닝 트리를 이용한 방식이다.모든 섬이 같은 그룹에 포함되는 순간 멈추는 것이 최소 스패닝 트리이므로, 이후 a에서 b까지 가려면 그 경로를 복원해서 사용하는 방식으로 접근하려고 했다.하지만 a와 b가 같은 그룹이 되는 순간의 간선의 가중치가 바로 최소 가중치가 되므로 그 구간에서 바로 출력 후 종료한다.그렇게 하기 위해 간선 정보를 간선의 가중치를 기준으로 내림차순으로 정렬한 후 유니온 파인드를 진행한다.마지막으로, a와 b가 같은 그룹이 되지 못하는 경우에..
백준/오늘의 문제 2025. 1. 2. 13:52
이전 Prev 1 Next 다음