꿀잠

https://leetcode.com/problems/min-cost-to-connect-all-points/description/

좌표의 거리가 가장 가까운 거리에 있는 좌표끼리 이어주는 문제이다. 최소신장트리 알고리즘이 필요한 문제이다. 좌표간의 거리는 일반적인 거리가 아닌 manhattan distance를 이용해야 하며 문제에서 수식이 주어진다.

최소 신장 알고리즘에는 프림 알고리즘과 크루스칼 알고리즘이 대표적이다. 그 중 프림 알고리즘을 이용하여 풀어주었다.

프림 알고리즘은 임의의 한 지점부터 가장 가까운 거리에 있는 지점을 이어주면서 순차적으로 방문한 지점들을 visited로 체크해주는 방식이다. 순차적으로 가까운 거리를 이어주기 위해서 PriorityQueue를 사용해 주었고 주어진 수식을 이용하기 위해 Comparable을 구현한 클래스를 만들어주었다.

import java.util.*;  
  
public class Solution {  
    public int minCostConnectPoints(int[][] points) {  
  
        int answer = 0;  
        boolean[] visited = new boolean[points.length];  
        PriorityQueue<Edge> pq = new PriorityQueue<>();  
        pq.add(new Edge(0, 0, points));  
  
        while(!pq.isEmpty()){  
            Edge edge = pq.poll();  
            int cur = edge.to;  
            if(visited[cur]) continue;  
            visited[cur] = true;  
            answer += edge.dist;  
  
            for(int next = 0; next < points.length; next++){  
                if(next == cur) continue;  
                if(!visited[next]){  
                    pq.add(new Edge(cur, next, points));  
                }  
            }  
        }  
  
        return answer;  
    }  
  
    private static class Edge implements Comparable<Edge>{  
        int from;  
        int to;  
        int dist;  
  
        Edge(int from, int to, int[][] points){  
            this.from = from;  
            this.to = to;  
            this.dist = manDist(points[from], points[to]);  
        }  
  
        private int manDist(int[] from, int[] to){  
            int xCalc = Math.abs(from[0] - to[0]);  
            int yCalc = Math.abs(from[1] - to[1]);  
            return xCalc + yCalc;  
        }  
  
        @Override  
        public int compareTo(Edge o){  
            return this.dist - o.dist;  
        }  
  
    }  
  
}