[200421] 탐욕법(Greedy) - 섬 연결하기(level3)

1. 문제 이해

- n개의 섬이 하나의 그룹으로 연결되도록! --> 비용이 최소가 되는 solution

- [섬1, 섬2, , cost]

 

2. 전략

- 비용이 최소인 경로를 우선적으로 연결

- edge의 개수는 n-1개로 고정되야 최소값을 유지할 수 있다.

- 조건 : 한 쪽만 연결되지 않은 경우만 경로에 추가

(모두 연결 - cycle 형성. edge의 개수가 n-1개를 넘어감)

(모두 연결X - 모두 연결에서 예외가 발생, 순서를 다음으로 넘긴다. / 어려웠던 예외case!!)

 

3. 참고했던 사항&기타사항

- 2차원 배열의 정렬

Arrays.sort(costs, Comparator.comparingInt(o1 -> o1[2])); //o1의 3번째 요소에 따라 comparingInt
for(int i= 1; i < costs.length; i++){
	indexList.add(i);
}

- 모두 연결X경우의 예외 처리 --> 후보군의 index만 들어있는 배열 형성

 

4. 코드

import java.util.*;

class Solution {
    public int solution(int n, int[][] costs) {
        int answer = 0;
        HashSet<Integer> check = new HashSet<>();
        ArrayList<Integer> indexList = new ArrayList<>();
        
        //2차원 배열 정렬**
        Arrays.sort(costs, Comparator.comparingInt(o1 -> o1[2]));
        for(int i= 1; i < costs.length; i++){
            indexList.add(i);
        }
        //최소값으로 엣지 하나 연결
        check.add(costs[0][0]); check.add(costs[0][1]);
        int edge = 1;
        answer += costs[0][2];
        int target = 0;
        //한 쪽만 연결되지 않은 경우만 엣지로 추가
        while(edge < n-1 && target < costs.length){
            int index = 0;
            target = indexList.get(index);
            int a = costs[target][0];
            int b = costs[target][1];
            if(check.contains(a) && check.contains(b)){ //모두 연결
                indexList.remove(index);
                continue;
            }
            while((!check.contains(a) && !check.contains(b)) || 
                 (check.contains(a) && check.contains(b))){ //모두 연결안됨
                index++;
                target = indexList.get(index);
                a = costs[target][0]; b = costs[target][1];
            }
            indexList.remove(index);
            check.add(a); check.add(b);
            edge++;
            answer += costs[target][2];
        }
        boolean[] b = new boolean[4];
        int[] k = new int[4];
        System.out.println(k[0] + " " + b[0] + " " + b.length);
        return answer;
    }
}