Lv 3. 섬연결하기

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

프로그래머스

 

 

유니온파인드, 크루스칼 알고리즘을 활용하여 문제를 풀었다.

제시된 N개의 꼭지점의 시작점과 끝점 가중치가 주어졌을때 

주어진 시작점,끝점,가중치 가 담긴  costs 2차원배열을 Arrays.sort() 

활용하여 가중치기준으로 오름차순 기준 정렬을 해준다.

union find method를 구현하고 parent 배열을 구현하여 

정렬된 costs 배열을 순회하면서 두 시작점과 끝점이 연결되어있다면 pass

연결되지 않았다면 union method 호출 하여 연결후 가중치를 answer에 더한다.

마지막으로 answer를 return하여 문제 해결 하였다.

 

 

package Programmers;

import java.util.*;

class p섬연결하기 {
    private int[] p;
    private int find(int a){
        if(p[a]==a) return a;
        return p[a] = find(p[a]);
    }
    private void union(int a, int b){
        a = find(a);
        b = find(b);
        if(a != b) p[b] = a;
    }
    public int solution(int n, int[][] costs) {
        p = new int[n];
        for(int i = 0 ; i < n ; i++)
            p[i] = i;

        Arrays.sort(costs,(o1,o2)-> o1[2]-o2[2] );
        int answer = 0;
        for(int i = 0 ; i < costs.length ; i++){
            if(find(costs[i][0]) != find(costs[i][1])){
                union(costs[i][0],costs[i][1]);
                answer += costs[i][2];
            }
        }
        return answer;
    }
}