[JAVA] 섬 연결하기 (코딩테스트 고득점 Kit [ Greedy(탐욕법) ]) - LEVEL3

📂 문제 설명

 

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

제한사항

• 섬의 개수 n은 1 이상 100 이하입니다.
• costs의 길이는 ((n-1) * n) / 2이하입니다.
• 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
• 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

입출력 예

ncostsreturn

4

[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]

4

입출력 예 설명

costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

 

---

📂 알고리즘 및 아이디어(문제풀이)

• 섬과 섬을 연결하여 최소한의 비용으로 모든 섬을 연결해야 하는 문제이다.
• 최소 비용으로 섬을 연결하기 위해서 다리 건설 비용(costs)에 대해서 오름차순으로 재정렬 해준다.
  • Arrays.sort() 를 응용해 cost로만 비교해준다. return 값이 true면 앞에 false면 뒤로 옮겨준다.
•   섬과 섬을 연결할때 연결되어 있는 상태를 알기 위해서 부모 노드를 통해서 구분 해준다.(링크로 가면 쉽게 설명되어 있다.)
  • 여기서 알아야 할 것은 "Union - find(합집합 찾기)" 와 "크루스칼 알고리즘" 을 알면 쉽게 구할 수 있다.
  •  초기값으로 모든 배열에 부모노드는 자신으로 설정해준다.
  • for문을 통해 배열을 비교해 나가면서 부모 노드를 비교하여 같은 부모를 가지고 있으면 두 섬은 연결되어 있음을 나타내고
  • 그렇지 않으면 서로 연결되어 있지 않은 것을 의미하고 이때 "answer += 건설 비용" 을 더해준다. 
  • 위 경우에는 Union 을 통해 낮은 부모 노드값이 낮은 곳으로 연결한다.
  • 부모 노드가 같은지 비교할 때는 find(=GetParent() )를 통해서 구해준다.
• 마지막으로 answer값을 출력하면 섬 연결에 대한 최소 비용이 나온다.

📂 소스 코드

import java.util.Arrays;
class Solution {
   public int solution(int n, int[][] costs) {
	        int answer = 0;
	        
	        //cost에 대해서 오름차순으로 정리해준다. 
	        Arrays.sort(costs, (o1,o2)->{
	        	return o1[2]-o2[2];
	        });	        
	        
	        // 부모 노드를 생성한다. 
	        int parent[] = new int[n];
	        for(int i=0;i<n;i++) parent[i]=i;
	        
	        for(int[] cost : costs) {
	        	int value = cost[2];
	        	int A = cost[0];
	        	int B = cost[1];
	        	
	        	if(GetParent(parent, A) == GetParent(parent, B)) { //이미 연결된걸 의미한다. 
	        		continue;
	        	}else {           //부모 노드가 같지 않으면 서로 연결된게 없는걸 의미하므로 연결해준다.
	        		Union(parent, A, B);
	        		answer+=value;
	        	}	
	        }
	        return answer;
	    }	
	
	    public static void Union(int[] parent , int A, int B ) {
	    	A = GetParent(parent, A);
	    	B = GetParent(parent, B);
	    	if(A<B) {
	    		parent[B]=A;
	    	}else {
	    		parent[A]=B;
	    	}	
	    }   
	   public static int GetParent(int[] parent, int who) {
		   if(parent[who] == who) return who;
		   return GetParent(parent, parent[who]);
	   }
}

 

📂 후 기 

어디서 많이 봤던 문제 였나 싶었더니 역시나 예전에 풀었던 문제였다. 쉽게 풀릴줄 알고 하다가 계속 꼬이더니 정체가 됐었다ㅠㅠ.  그래서 예전에 풀었을때 크루스칼 알고리즘으로 했던게 떠올라서 풀었던걸 참고하여 다시 풀게 되었다.

프로그래머스 kit를 다 풀고 나서는 알고리즘을 정리해서 까먹었던 부분이나 필요한 부분을 블로그에 올려야 겠다.