[ 프로그래머스 / Programmers Level 3 ] 섬 연결하기 ( JAVA / 자바 )

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

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

 

문제

---

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

제한 사항

---

• 섬의 개수 n은 1 이상 100 이하입니다.
• costs의 길이는 ((n-1) * n) / 2이하입니다.
• 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
• 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

풀이

---

Prim 알고리즘 으로 해결 ‼️

https://hyeyun.tistory.com/entry/Algorithm-알고리즘-Prims-Algorithm-프림-알고리즘

[ Algorithm / 알고리즘 ] Prim's Algorithm ( 프림 알고리즘 )

코드

---

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class 섬연결하기 {

    static class bridge implements Comparable<bridge>{
        int start;
        int destination;
        int cost;

        bridge(int start, int destination, int cost){
            this.start = start;
            this.destination = destination;
            this.cost = cost;
        }

        @Override
        public int compareTo(bridge o) {
            return this.cost - o.cost;
        }

    }

    static ArrayList<bridge> adj[];
    static ArrayList<bridge> mst;
    static boolean[] isVisited;

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

        adj = new ArrayList[n];
        mst = new ArrayList<>();
        isVisited = new boolean[n];

        for(int i = 0 ; i < n; i++){
            adj[i] = new ArrayList<>();
        }

        for(int[] c : costs){
            adj[c[0]].add(new bridge(c[0], c[1], c[2]));
            adj[c[1]].add(new bridge(c[1], c[0], c[2]));
        }

        PriorityQueue<bridge> pq = new PriorityQueue<>();
        Queue<Integer> queue = new LinkedList<>();
        
        queue.offer(0);
        mst.add(new bridge(-1, 0, 0));
        isVisited[0] = true;

        while(!queue.isEmpty()){
            int now = queue.poll();
            
            for(bridge b : adj[now]){
                if(!isVisited[b.destination])
                    pq.offer(b);
            }

            while(!pq.isEmpty()){
                bridge b = pq.poll();

                if(!isVisited[b.destination]){
                    queue.add(b.destination);
                    isVisited[b.destination] = true;
                    mst.add(b);
                    answer += b.cost;
                    break;
                }
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        int[][] costs = {{0,1,1}, {0,2,2}, {1,2,5}, {1,3,1}, {2,3,8}};
        System.out.println(solution(4, costs));
    }
}