PS/프로그래머스
[ 프로그래머스_Lv3 ] 섬 연결하기 ( 크루스칼 - 자바스크립트 )
문제 https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr How to Solve ? [1] 문제에 들어 가기 전에 이 문제를 풀기 위해서는 최소 스패닝(=신장) 트리를 해결 하기 위한 [ 크루스칼 / 프림 ] 알고리즘을 이해 하신 후에 풀 수 있는 문제라고 생각합니다. 1-1 ) 크루스칼 크루스칼은 '선'을 기준으로 최소 신장 트리를 찾는 알고리즘으로써, 선의 길이를 오름차순으로 정렬 한뒤 아래의 그림과 같이 순서대로 선을 연결 합니다. 다음과 같이 선을 연결하며, 찾을 때 발생 할 수 있는 문제는 "사이클이 ..
2021. 6. 20.