[프로그래머스 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 최소비용으로 n개의 섬이 모두 연결될 수 있도록 하는 문제. 풀이 다리를 통해서 통행이 가능하다면 두 섬은 연결되어있다고 본다. 문제를 보면 최소스패닝 트리 문제인 것을 알 수 있다. 최소 스패닝 트리를 이용해서 모든 섬이 공통 조상을 가지도록 연결시켜주면 된다. 코드 작성 #include #include #include using namespace std; const int MAX_N = 100 + 5; int Parent[MAX_N]; int F..
2022. 6. 23.