[프로그래머스] 섬 연결하기 / JAVA / Kruskal's Algorithm / Prim's Algorithm

> 문제 설명 보기

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

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

>IDEA

Minimum Spanning Tree(MST)를 구하는 문제이다.

정점을 기준으로 MST를 구하는 Prim의 알고리즘과 간선을 기준으로 MST를 구하는 Kruskal의 알고리즘으로 해당 문제를 해결 할 수 있다.

해당 문제의 input이 간선으로 주어졌으므로, Kruskal의 알고리즘의 코드가 더 짧다.

 

>Solution (Kruskal's Algorithm)

import java.util.*;

class Solution {
    public int solution(int n, int[][] costs){
        int answer = 0;
        int[] fromIsland = new int[n];

        // 모든 간선을 가중치 오름차순으로 정렬
        Arrays.sort(costs, (o1, o2) -> o1[2] - o2[2]);

        for(int idx = 0; idx < n; idx ++){
            fromIsland[idx] = idx;
        }

        for(int[] cost : costs){
            if(findRoot(cost[0], fromIsland) != findRoot(cost[1], fromIsland)){
                fromIsland[findRoot(cost[0], fromIsland)] = findRoot(cost[1], fromIsland);

                answer += cost[2];
            }
        }

        return answer;
    }

    int findRoot(int nodeNo, int[] fromIsland){
        if(fromIsland[nodeNo] == nodeNo) return nodeNo;
        return findRoot(fromIsland[nodeNo], fromIsland);
    }
}

> Result (Kruskal's Algorithm)

 

> Solution (Prim's Algorithm)

public int solution(int n, int[][] costs) {
        int answer = 0;

        HashMap<Integer, ArrayList<int[]>> edgeMap = new HashMap<>();
        HashSet<Integer> nodes = new HashSet<>();
        ArrayList<int[]> edges = new ArrayList<>();

        for(int[] cost : costs){
            if(edgeMap.containsKey(cost[0])){
                edgeMap.get(cost[0]).add(new int[]{cost[1], cost[2]});
            } else {
                ArrayList<int[]> insertList = new ArrayList<>();
                insertList.add(new int[]{cost[1], cost[2]});
                edgeMap.put(cost[0], insertList);
            }
            if(edgeMap.containsKey(cost[1])){
                edgeMap.get(cost[1]).add(new int[]{cost[0], cost[2]});
            } else {
                ArrayList<int[]> insertList = new ArrayList<>();
                insertList.add(new int[]{cost[0], cost[2]});
                edgeMap.put(cost[1], insertList);
            }
            nodes.add(cost[0]);
            nodes.add(cost[1]);
        }

        int node = costs[0][0]; // 시작 노드
        edges.addAll(edgeMap.get(node));
        nodes.remove(node);

        while(!nodes.isEmpty()){
            Collections.sort(edges, (o1, o2) -> o1[1] - o2[1]);
            for(int idx = 0; idx < edges.size(); idx++){
                int[] edge = edges.get(idx);
                if(nodes.contains(edge[0])){
                    nodes.remove(edge[0]);
                    edges.remove(idx);
                    edges.addAll(edgeMap.get(edge[0]));
                    answer += edge[1];
                    break;
                }
            }
        }

        return answer;
    }

> Result (Prim's Algorithm)

 

Prim의 알고리즘이 더 느려보이지만 구현방식에 있어 Collection 객체가 많이 사용되어서 그렇고, 사실은 두 알고리즘의 시간복잡도는 똑같다.