[프로그래머스] 섬 연결하기(Java, Greedy, Lv3)

programmers.co.kr/learn/courses/30/lessons/42861

코딩테스트 연습 - 섬 연결하기

 

 

## 접근방법

---

섬을 최소의 비용으로 연결해야 한다. 이 문제를 보자마자 최소 신장트리의 개념이 떠올랐다. 가장 거리가 짧은 것들 부터 추가하면, 최소의 비용으로 모든 섬들을 연결할 수 있다.

 

 

 

그리디에서 자주 출제되는 유형은, 가장 거리가 짧은 것부터 찾아서 전역적 최적해를 찾는 방식이 자주 나오는 거 같다. 본론으로 돌아가서, 크루스칼 알고리즘을 이용하면 쉽게 문제를 해결할 수 있다.

 

 

 

처음에 시행착오를 소개하자면, 다리 비용을 기준으로 오름차순으로 정렬을 마쳤지만, 섬을 방문할지 결정하는 로직을 단순히 체크 배열로 했었다.

 

 

 

둘다 이미 방문됐다면, 방문될 필요가 없어서 이런 아이디어를 떠올렸다. 하지만, 이것은 틀린 생각이다. 섬이 연결되지 않았더라도, 다른 다리에 의해서 섬들이 체크될 수 있으므로, 모든 섬들을 연결할 수가 없다.

 

 

 

모든 섬들을 다리로 연결해야 한다. 섬 방문 여부를 확인하는 체크 배열의 이용이 아니라, 유니온 파인드로 문제를 해결해야 한다. 유니온 파인드는 여러 섬들을 하나의 집합으로 묶어주고, 사이클이 생성되지 않게 도와준다.  사이클은 이미 연결된 섬들에 불필요한 다리를 추가하는 것이므로 생성되지 않아야 최소 비용으로 모든 섬들을 연결할 수 있다.

 

 

 

유니온 파인드와 우선순위큐를 이용해서 쉽게 풀 수 있는 문제이다.

 

 

 

## 해설코드

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

import java.util.*;   class Solution {     int[] parent;          class Item{         int node1, node2, cost;         Item(int n1, int n2, int c){             this.node1 = n1;             this.node2 = n2;             this.cost = c;         }         }          int find(int num){         if(parent[num] == num)             return num;         else             return parent[num] = find(parent[num]);      }          void union(int a, int b){         parent[find(a)] = find(b);     }          public int solution(int n, int[][] costs) {         int answer = 0;         PriorityQueue<Item> pq = new PriorityQueue<>((a,b) -> (a.cost - b.cost));         parent = new int[n];                  for(int i = 0; i < parent.length; i++)             parent[i] = i;                  for(int i = 0; i < costs.length; i++){             int n1 = costs[i][0];             int n2 = costs[i][1];             int c = costs[i][2];                          pq.add(new Item(n1, n2, c));         }                  while(!pq.isEmpty()){             Item item = pq.poll();                          if(find(item.node1) == find(item.node2)) continue;                          union(item.node1, item.node2);             answer += item.cost;         }                           return answer;     } } Colored by Color Scripter