[프로그래머스] (Greedy)섬 연결하기 (C++)
섬 연결하기 (Level 3) 문제 전체 문제 보기 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 접근법 최소 비용 신장 트리 이번 문제는 두 가지 방법으로 풀었다. 처음 접근하는 방법은 동일하고 구현하는 방법에서 차이가 있기 때문에 공통된 부분을 설명한 뒤 두 가지 풀이법을 모두 다뤄본다. 문제에서 요구하는 바는 모든 섬을 가장 적은 비용으로 연결했을 때의 비용이다. 이를 자료구조에서는 최소 비용 신장 트리 (MST)라고 한다. 이에 대한 설명은 예전에 다룬 글이 있어 링크를 남긴다. 간략하게만 정리하면 최소 비용 신장 트리는 신장 트리의 일종인데, 먼저 신장 트리가 되기 위해서는 다음의 조건을 만족해야..
