Union-find (1) 썸네일형 리스트형 [프로그래머스] 섬 연결하기 / Minimum Spanning Tree, Kruskal MST, Union-find / C++ 풀이 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 전략 n개의 섬을 최소한의 비용으로 전부 연결해야 한다. 최소 신장 트리(Minimum spanning tree)는 그래프의 정점들을 최소의 비용으로 전부 연결한다. 이 때, n개의 정점에 대해 (n-1)개의 간선을 사용하여 연결한다. Kruskal MST 알고리즘 비용이 가장 적은 간선부터 n개의 정점을 전부 연결 할 때까지 선택해 나간다. 서로 연결된 정점들은 하나의 '그룹'이.. 이전 1 다음
