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

https://programmers.co.kr/learn/courses/30/lessons/42861?language=java 

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

Greedy 알고리즘은 부분적인 최적해를 계속 확장 시켜서 전제적인 최적해를 찾는 알고리즘 입니다.

연결할 노드 A, B와 비용 c가 들어있는 costs 배열이 주어졌을때, 비용 c 를 들여 노드 A, B 를 연결해야 하는지를 판단하는 부분이 핵심입니다. 만약 두개의 노드가 이미 직접적으로든/ 혹은 우회적으로든 연결되어 있다면, 굳이 추가 비용을 들여 A,B 를 연결할 필요가 없습니다.

A 와 B 가 이미 연결되어 있는 경우

반면 노드 A, 노드 B 가 서로 다른 노드와는 연결되어 있지만 각자의 노드 집합들이 연결되어 있지 않은 경우는 A 와 B 사이에 다리를 연결 해주는 것이 좋습니다. 그렇게 되면 기존에 A와 직접적으로 혹은 간접적으로 연결되어 있던 모든 노드들이 B 와 연결되게 됩니다. 

위 조건들을 set 을 이용하여 코드로 구현하면 다음과 같습니다. 

import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

class Solution {
    public int solution(int n, int[][] costs) {
        int answer = 0;
        Arrays.sort(costs, (int[] a, int[] b) -> Integer.compare(a[2], b[2]));
        Set<Set<Integer>> areaSet = new HashSet<>();
        for (int[] cost : costs) {

            if (areaSet.size() == 1 && areaSet.iterator().next().size() == n) {
                break;
            }

            Set<Integer> lSet = new HashSet<>();
            Set<Integer> rSet = new HashSet<>();
            boolean alreadyHave = false;
            for (Set<Integer> nodeSet : areaSet) {
                if ((nodeSet.contains(cost[0]) && nodeSet.contains(cost[1]))) {
                    // 같은 set 에 있는 경우
                    alreadyHave = true;
                    break;
                } else if (nodeSet.contains(cost[0])) {
                    // 다른 set 에 있는 경우
                    lSet = nodeSet;
                } else if (nodeSet.contains(cost[1])) {
                    // 다른 set 에 있는 경우
                    rSet = nodeSet;
                }
            }

            if (lSet.isEmpty() && rSet.isEmpty()) {
                // 아예 새로운 조합인 경우
                if (!alreadyHave) {
                    Set<Integer> newSet = new HashSet<>();
                    newSet.add(cost[0]);
                    newSet.add(cost[1]);
                    areaSet.add(newSet);
                    answer += cost[2];
                }
            } else if (!lSet.isEmpty() && rSet.isEmpty()) {
                lSet.add(cost[1]);
                answer += cost[2];
            } else if (lSet.isEmpty() && !rSet.isEmpty()) {
                rSet.add(cost[0]);
                answer += cost[2];
            } else {
                for (Iterator<Set<Integer>> iter = areaSet.iterator(); iter.hasNext(); ) {
                    if (iter.next().equals(rSet)) {
                        iter.remove();
                        break;
                    }
                }
                lSet.addAll(rSet);
                answer += cost[2];
            }
        }
        return answer;
    }
}

다른 풀이 

위의 코드에서 Iterator 를 이용해서 삭제하는 부분에서 이질감이 느껴집니다. hashSet에서 remove 가 정상적으로 작동하지 않아서 임시방편으로 고쳐놓은 코드입니다 (작동하지 않은 이유는 아직 불명확해서 확인후에 포스트 업데이트 하겠습니다.) 

위 문제를 해결하기 위해서 다른 분들에게 질문하던 중, 해당 문제가 Minimum Spanning Tree 라는 유명한 알고리즘 예제라는 것을 알게되었습니다. 사실상 유형이 정해진 문제였네요. Minimum Spanning Tree 관련해서 학습한후에 다른 풀이 코드 첨부하겠습니다