[programmers] 섬 연결하기

---

로직

1. 비용이 최소화되어야하므로 비용 기준으로 정렬시킨 후 연결된 지점들을 찾는다.

2. 정렬된 costs의 처음값의 시작점을 visit에 표시한다. visit을 확인하면서 시작점 또는 끝점이 지나간 경험이 있으면 연결하려 시도한다.

3. 만약 시작점, 끝점이 다 지나왔으면 그냥 넘기고, 한쪽만 지나왔으면 visit을 체크한 후, 비용을 더해준다.

4. 그냥 비용을 더해도 괜찮은 이유는 비용 기준으로 정렬했기때문!

 

코드

 

주의할 점

1. break를 작성해줘야하는 이유!

  -> break를 사용해야 for문이 끝나고 for문을 계속 새로 실행하면서 if visit and visit에 걸려서 continue로 else문에 도착한다.
       1 2 1 2 3 2 1 2 3 2 3 2
  -> break 사용하지 않으면 1 2 2 2 2 3 2 3 -> 모든 cost의 값들을 사용하지 못할 수 있음