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

https://programmers.co.kr/learn/courses/30/lessons/42861#

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

2021-08-14

---

MST 알고리즘

 

1. 크루스칼 알고리즘

import java.util.*;
class Solution {
   static int[] parent;
    static int find(int x) {
        if(x == parent[x]) return x;
        return parent[x] = find(parent[x]);
    }
 
    static void union(int x, int y) { // y > x
        x = find(x);
        y = find(y);
 
        if(x != y) parent[y] = x;
    }
 
    static int solution(int n, int[][] costs) {
        int answer = 0;
        // 1) 간선 리스트의 가중치를 기준으로 오름차순 정렬
        Arrays.sort(costs, Comparator.comparingInt(o -> o[2]));
 
        // union-find (parent[] init)
        parent = new int[n];
        for(int i = 0; i < n; i++) parent[i] = i;
 
        // 2) 가중치가 작은 간선부터 선택
        for(int i = 0; i < costs.length; i++) {
            int start = costs[i][0];
            int end = costs[i][1];
            int weight = costs[i][2];
 
            // 3) 부모노드가 같지 않은 경우 연결
            if(find(start) != find(end)) {
                if(start > end) {
                    int tmp = end;
                    end = start;
                    start = tmp;
                }
                union(start, end);
                answer += weight;
            }
        }
 
        return answer;
    }
}

#문제풀이

크루스칼 알고리즘

union 따로 함수로 안 빼고, find에서 나온 값들을 바로 parent[end] = start 이런식으로 넣어도 된다.

 

 

 

2. 프림 알고리즘

import java.util.*;
class Solution {
 static class Edge {
        int target;
        int weight;
 
        public Edge(int target, int weight) {
            this.target = target;
            this.weight = weight;
        }
    }
    static int solution(int n, int[][] costs) {
       int answer = 0;
        // 가중치 오름차순 정렬
        PriorityQueue<Edge> pq = new PriorityQueue<>((o1, o2) -> o1.weight - o2.weight);
        List<List<Edge>> list = new ArrayList<>();
 
        // init
        for(int i = 0; i <= n; i++) list.add(new ArrayList<>());
 
        for(int i = 0; i < costs.length; i++) {
            list.get(costs[i][0]).add(new Edge(costs[i][1], costs[i][2]));
            list.get(costs[i][1]).add(new Edge(costs[i][0], costs[i][2]));
        }
 
        boolean[] vtd = new boolean[n];
 
        //임의의 정점 하나 선택
        pq.add(new Edge(0,0));
        
        while(!pq.isEmpty()) {
            Edge e = pq.poll();
            if(vtd[e.target]) continue;
            vtd[e.target] = true;
            answer += e.weight;
 
            for(Edge edge: list.get(e.target)) {
                if(!vtd[edge.target]) pq.add(new Edge(edge.target, edge.weight));
            }
        }
 
        return answer;
    }
 
}

#문제풀이

프림 알고리즘