[프로그래머스] 섬 연결하기 (C++)
1. 문제 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 2. 풀이 네트워크와 비슷해보이지만 MST문제로 크루스칼 알고리즘을 사용해야한다. 1) 비용이 작은 순으로 정렬한다. 2) 최소 비용으로 다리를 연결하고 싸이클이 생기는지 확인한다. 1번 섬과 2번 섬이 연결되면 island[1] = 2, island[2] = 1이 된다. 3) 싸이클이 생기지 않으면 두 섬 사이에 다리를 연결한다. 1) ~ 3) 을 costs 길이만큼 반복!! *크루스칼 알고리즘: https://hyeri0903.tistory.co..
2021. 9. 6.
