크루스칼1 [백준, 13905, G4, MST] 세부 0. 문제 링크 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 1. 문제 핵심 그래프 탐색을 하며 출발지부터 목적지까지 경로를 탐색하는 중에 가장 빼빼로를 많이 들고갈 수 있는 경로를 탐색하는 문제입니다. 2. 문제 접근 그래프 탐색이기 때문에 별 생각없이 다익스트라를 사용했습니다. 다익스트라를 사용했을 때 가지치기를 적절히 사용해준다면 문제는 풀립니다. 하지만 자바 1등과 시간 차이가 커서 다른 방법.. 2022. 10. 18. 이전 1 다음