23.03.02 파이썬 코딩 퀴즈#181 섬 연결하기(프로그래머스 스쿨)

이번 문제는 섬 연결하기 이다.

n 개의 섬 사이에 다리를 건설하는 비용 costs 가 주어질 때, 최소 비용으로 모든 섬이 통행 가능하도록 만들고, 이때 필요한 최소비용은 반환해야 한다.

중요한건 다리를 건설하는 비용인 costs 이며, costs[i]를 기준으로 [0] 과 [1] 은 서로 연결된 섬 번호를 의미하며, [2]는 다리르 건설할 때 드는 비용을 의미한다.

즉, 거리를 계산하는게 아닌 모든 섬이 연결 가능한 다리들의 조합을 만들고, 건설 비용이 최소가 되는 방법을 찾아야 한다.

입출력 예를 살펴보면 좀더 정확하게 이해할 수 있다.

총 4개의 섬이 있으며, [0,1], [0,2],[1,3] 을 연결하면 모든 섬들이 연결된 다리가 건설 가능하고, 이때 최소 비용은 1, 2, 1 인 4가 된다.

 

해당 문제에서 확인해야 할 부분은 두가지이다.

1. 최소 비용으로 다리 건설하기

2. 건설된 다리를 통해 모든 섬을 연결하기

 

먼저 최소 비용으로 다리를 건선하기 위해 비용을 기준으로 오름차순 정렬하여 주고 시작한다.

다음 connected 를 set()을 이용하여 만들어주고 최초 값은 정렬된 costs[0][0] 값을 넣어준다.

이제 다리를 건설해 보자.

만약 두 섬이 이미 연결된 경우라면 continue 로 건너띄게 된다.

그리고 시작섬으로 부터 하나만 연결된 경우라면, update()를 통해서 좌표형태로 값을 connected에 전달한다.

그리고 cost[2]를 answer에 더해주는데, 이 때 중요한것은 break로 해당 반복문을 종료한다는 것이다. 이유는 단순하다.

해당 costs는 비용을 기준으로 오름차순 되어 있다. 하지만 이는 첫번째 섬에 연결된 경우에만 유효하다.

즉 for문을 통해 처음 3번 섬이 연결되었다면 connected = {0,3} 이 되고, 그 뒤에 나오는 더 높은 값을 넣는 오류가 발생한다. 

예를 들어 costs = [[0, 1, 5], [0, 3, 2], [0, 4, 3], [1, 4, 1], [3, 4, 10], [1, 2, 2], [2, 5, 3], [4, 5, 4]]  라고 가정하자.

순서에 따라 비용을 기준으로 오름차순 정렬하면 [[1, 4, 1], [0, 3, 2], [1, 2, 2], [0, 4, 3], [2, 5, 3], [4, 5, 4], [0, 1, 5], [3, 4, 10]] 이 된다.

그리고 connected = {1} 에서 시작한다. break 없이 계속 탐색을 진행한다고 가정하면

costs[0] 은 조건에 맞다. 따라서 connected = {1,4} 가 된다.  

그 다음은 costs[2] 이다. connected = {1,4,2} 가 되었다.

다음은 costs[3] 이다. connected = {1,4,2,0} 이다.

그리고 다음은 costs[4] 이고 마지막은 costs[6] 이다. 

하지만 이를 break를 통해 갱신된 connected를 처음부터 탐색하게 되면, costs[1] 으로 연결된 다리를 선택하게 된다.

 

따라서 반드시 break로 처음부터 다시 탐색을 하는게 중요하다.