<Algorithm> 184. 섬연결하기(Programmers)

1. 섬연결하기(Programmers)

   사용 알고리즘 : MST(prim), 우선순위 큐, 그리디 

• 처음에 보자마자 MST문제라고 느낌이 왔었는데 그리디 카테고리로 분류 되어있어서 다른 방법이 있는 줄 알았다 .... 

• MST 알고리즘을 살펴보면 그리디 인것을 알 수 있는데 순간마다 최적(cost가 작은) 경로를 선택하는 방법이라서 그렇다.

• MST는 https://www.crocus.co.kr/733 여기에 아주 자세~하게 잘 나와있다.. 

문제에 대한 접근&생각

1. 최소 비용으로 모든 섬이 연결 가능하게 -> MST!

내 코드 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.PriorityQueue;   class Solution {     static List<Node>[] map;     public int solution(int n, int[][] costs) {         /***************************          * prim 알고리즘을 이용해서 MST를          * 구하고 그 가중치 총합을 출력한다.          ***************************/         map = new ArrayList[n];         for(int i = 0; i < n; i++)             map[i] = new ArrayList<>();         for(int i = 0; i < costs.length; i++) {             int a = costs[i][0];             int b = costs[i][1];             int c = costs[i][2];             map[a].add(new Node(b, c));             map[b].add(new Node(a, c));         }         vistied = new boolean[n];         dist = new int[n];         prim();                  return Arrays.stream(dist).sum();     }     static int[] dist;     static boolean vistied[];      private static void prim() {                 PriorityQueue<Node> pq = new PriorityQueue<>(Node::compare);                  Arrays.fill(dist, 99999);         dist[0] = 0;         pq.add(new Node(0, dist[0]));         while (!pq.isEmpty()) {             Node node = pq.remove();             if(vistied[node.vertax]) continue;             vistied[node.vertax] = true;             // 여기에 방문설정하는 이유는 양방향성 떄문에             // 왔던길 돌아가는 것을 방지하기 위함이다.             // 자신이 기준점이 되는 순간에 자신과 가장 가까운             // 거리를 알 수있기 때문에 더이상 방문할 필요가 없다.             for(Node adj : map[node.vertax]) {                 if(!vistied[adj.vertax]) {                     if(dist[adj.vertax] > adj.cost) {                         pq.add(new Node(adj.vertax, adj.cost));                         dist[adj.vertax] = adj.cost;                     }                 }             }         }     }     static class Node{         int vertax,cost;         public Node(int vertax, int cost) {             super();             this.vertax = vertax;             this.cost = cost;         }         private static int compare(Node o1, Node o2) {             return Integer.compare(o1.cost, o2.cost);         }     } } Colored by Color Scripter

cs