분리집합1

• 

  [백준 1939] 중량제한, 크루스칼 풀이 🔗 문제링크 🔗 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 🌟 생각 흐름 🌟 기존의 크루스칼 문제에서는 최단 경로를 계산하기 위해서 최단 경로를 기준으로 정렬을 하였다 하지만 해당 문제에서는 다리를 건널 때 가장 많이 적재할 수 있는 양을 물어보는 것이므로 가장 높은 값을 기준으로 정렬한다(내림차순) 만약 시작 지점과 끝지점이 한사이클안에 있다고 판단되는 순간 현재 적재량을 싫고 나를 수 있다는 소리이므로 멈추고 리턴한다. -- 이진탐색을 이용한.. 알고리즘/백준 2023. 5. 4.