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

처음 시도 했을  때에는 쉽게 풀릴 것 같았다. 

 

첫 번째 시도에는 costs 에서 가중치 기준 오름차순 정렬하여 단순하게 가중치가 작은 간선만을 연결하며 방문처리 하는 방식으로 구현하였지만 처참하게도 0점이었다.

두 번째 시도에는 섬들을 정점, 다리를 두 정점의 간선 가중치로 생각하고 모든 노드를 돌며 방문했다면 재귀를 종료하고, 방문하지 않은 노드라면 이동할 수 있는 다음 노드간의 가중치 중에서 최소값을 갖는 노드에 대해 해당 노드가 바로 직전에 지나온 노드가 아니라면 가중치를 answer에 더하는 방식으로 해결하려고 했는데 단 두개의 테스트(1, 8)만 통과했다.  

 

그 밖에 다른 방법들도 생각해봤지만 정답에 근접하는 느낌은 없었고, 내가 처음 접하는 유형일 수도 있겠다는 생각에 힌트를 찾고자 검색해보니 이 문제를 해결하기 위해서는 '최소 신장 트리'개념을 알고 있어야 한다는 것을 알게 되었다. 최소 신장 트리는 직접 구현해본적은 없지만 들어본 기억만 있는 상태였다.

 

 

 

따라서 최소 신장 트리 개념에 대해 간단하게 정리를 해보았다.

최소 신장 트리(Minimum Spanning Tree)

 

 

 

크루스칼 알고리즘을 사용한 풀이

import java.util.*;

class Solution {
    
    int[] parent;
    
    public int solution(int n, int[][] costs) {
        
        int answer = 0;
        
        parent = new int[n];
        for (int i=0; i<n; i++) parent[i] = i;
        
        Arrays.sort(costs, (a, b) -> {
            return a[2] - b[2];
        });
        
        for (int[] info : costs) {
            
            int from = info[0];
            int to = info[1];
            int cost = info[2];
            
            int fromParent = findParent(from);
            int toParent = findParent(to);
            
            if (findParent(from) == findParent(to)) continue;
            
            answer += cost;
            parent[toParent] = fromParent;
        }
        
        return answer;
    }
    
    private int findParent (int node) {
        if (parent[node] == node) return node;
        return findParent(parent[node]);
    }
}

 

 

프림 알고리즘을 사용한 풀이

import java.util.*;

class Solution {
    
    public int solution(int n, int[][] costs) {
        
        int answer = 0;
        
        List<int[]>[] list = new ArrayList[n];
        for (int i=0; i<n; i++) list[i] = new ArrayList<>();
        
        for (int[] info : costs) {
            int u = info[0];
            int v = info[1];
            int cost = info[2];
            list[u].add(new int[]{v, cost});
            list[v].add(new int[]{u, cost});
        }
        
        PriorityQueue<int[]> que = new PriorityQueue<>((a, b) -> {
            return a[1] - b[1];
        });
        
        boolean[] visited = new boolean[n];
        
        
        
        que.offer(new int[]{0, 0});
        
        while (!que.isEmpty()) {
            
            int[] arr = que.poll();
            
            int edge = arr[0];
            int cost = arr[1];
            
            if (visited[edge]) continue;
            
            visited[edge] = true;
            
            answer += cost;
            
            for (int[] temp : list[edge]) {
                if (!visited[temp[0]]) que.offer(temp);
            }
        }
        
        return answer;
    }
}

 

 

 

비슷한 문제

백준 1197번 최소 스패닝 트리

백준 1922번 네트워크 연결