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

문제

풀이

전형적인 크루스칼 알고리즘 풀이다.

 

1. Edge의 weight크기가 작은 순으로 정렬

 

2. Edge를 집합에 포함 시키기위해 find(x) 함수를 호출해서 parent가 같은지 확인

 

3. Parent가 같지 않은 Edge 한에서 Union을 호출하여 집합에 포함시킨 후 가중치 합을 반환

 

import java.util.*;
import java.io.*;
 
 
class Solution{
    static int[] parent;
    static ArrayList<Edge> list = new ArrayList<Edge>();
    static int answer=0;
    public int solution(int n,int[][] costs){
        parent = new int[n+1];
        for (int i=1;i<=n;i++)
            parent[i]=i;
        Arrays.stream(costs).map(e->new Edge(e[0],e[1],e[2]))
                .forEach(edge -> list.add(edge));
        Collections.sort(list);
 
        list.stream().filter(edge->find(edge.start) != find(edge.end))
                .forEach(edge -> union(edge.start, edge.end, edge.weight));
        return answer;
    }
    static int find(int x){
        if(x==parent[x])
            return x;
        parent[x] = find(parent[x]);
        return parent[x];
    }
    static void union(int x,int y,int weight){
        if(find(x)!=find(y))
            parent[find(x)] = y;
        answer+=weight;
    }
}
class Edge implements Comparable<Edge>{
 
    int weight;
    int start;
    int end;
 
    public Edge(int start,int end, int weight)
    {
        this.start=start;
        this.end=end;
        this.weight=weight;
    }
    @Override
    public int compareTo(Edge o) {
        // TODO Auto-generated method stub
        return this.weight-o.weight;
    }
}