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

문제 설명

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

문제 풀이

• 단순 최소 신장 트리 문제였다.
• 크루스칼 알고리즘, 프림 알고리즘으로 풀이하였다.

소스 코드 (JAVA, Kruskal 알고리즘)

import java.util.*;

class Solution {
    public int[] parent;
    
    public int find(int a) {
        if (parent[a] == a) return a;
        else return parent[a] = find(parent[a]);
    }
    
    public void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) 
            parent[b] = a;
    }
    
    public int solution(int n, int[][] costs) {
        //초기화
        parent = new int[n];
        for (int i = 0; i < n; i++)
            parent[i] = i;
        
        //크루스칼 알고리즘 
        Arrays.sort(costs, (o1, o2) -> o1[2] - o2[2]);
        int result = 0;
        for (int i = 0; i < costs.length; i++) {
            int a = costs[i][0];
            int b = costs[i][1];
            int val = costs[i][2];
            if (find(a) != find(b)) {
                union(a, b);
                result += val;
            }
        }
        
        return result;
    }
}

소스 코드 (JAVA, Prim 알고리즘)

import java.util.*;

class Solution {
    public class Point implements Comparable<Point>{
        int node, cost;
        
        public Point (int node, int cost) {
            this.node = node;
            this.cost = cost;
        }
        
        @Override
        public int compareTo (Point o) {
            return this.cost - o.cost;
        }
    }
    
    public List<List<Point>> map = new ArrayList<>();
    
    public int solution(int n, int[][] costs) {
        //초기화 
        for (int i = 0; i < n; i++)
            map.add(new ArrayList<>());
        for (int i = 0; i < costs.length; i++) {
            int from = costs[i][0];
            int to = costs[i][1];
            int val = costs[i][2];
            map.get(from).add(new Point(to, val));
            map.get(to).add(new Point(from, val));
        }
        
        //프림 알고리즘 
        boolean[] visit = new boolean[n];
        PriorityQueue<Point> q = new PriorityQueue<>();
        q.add(new Point(0, 0));
        
        int result = 0;
        while(!q.isEmpty()) {
            Point cur = q.poll();
            
            if (visit[cur.node]) continue;
            visit[cur.node] = true;
            result += cur.cost;
            
            for (int i = 0; i < map.get(cur.node).size(); i++) {
                int next = map.get(cur.node).get(i).node;
                int cost = map.get(cur.node).get(i).cost;
                if (visit[next]) continue;
                q.add(new Point(next, cost));
            }
        }
        
        return result;
    }
}