문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/42861

구현방법

각 다리를 건설하는 비용 cost가 존재 -> 양방향 연결

최소비용 신장 트리에대한문제이고 그 문제를 해결하는데 사용되는 알고리즘.

크루스칼알고리즘과 union-find알고리즘을 사용하자.

최소비용으로 구하기 때문에 비용을 기준으로 오름차순을 진행한다.

1. 부모가 같을 경우 -> 다리를 건설하지않음 -> 부모가 같다는건 이미 연결되있다는 거니까

2. 부모가 같지 않을 경우 0> 다리를 건설

3. 다리 비용을 합산

---

크루스칼 알고리즘에 대해서 알기전에는 어떻게 풀어야할지 감을 못잡았었는데 찾아보고나서 밑의 블로그에서 설명을 잘해주어서 이해할 수 있게되었다.

크루스칼 알고리즘에 대해서 설명해주는 블로그 : https://born2bedeveloper.tistory.com/31

힌트 참고 블로그 : https://born2bedeveloper.tistory.com/32

알고리즘

BFS + 구현!

CODE

import java.util.*;


class Solution {
    private int[] parent;


    public int solution(int n, int[][] costs) {
        int answer = 0;
        int index, j;
        parent = new int[n];

        //각 부모값들을 자기 자신으로 먼저 해둔다.
        for(index =0 ;index < parent.length;parent[index] = index++);
        //비용 기준 오름 차순 정렬진행
            Arrays.sort(costs, (o1, o2) -> {
                if(o1[2] > o2[2]){
                    return 1;
                }else
                    return -1;
            });

            //핵심로직
            for(index = 0; index <costs.length;index++){
                //둘이 부모가 같은 경우 -> 연결되어있음.
                if(get_parent(costs[index][0]) == get_parent(costs[index][1]))
                    continue;
                union(costs[index][0],costs[index][1]);
                //이게 되는 이유 -> 비용기준으로 오름차순 정렬을 했기 때문에
                answer += costs[index][2];
            }


        return answer;
    }

    //부모 찾기
    private int get_parent(int a){
        if(a == parent[a]){
            return parent[a];
        }else{
            return parent[a] = get_parent(parent[a]);
        }
    }
    //union-find 진행
    public void union(int a, int b){
        a = get_parent(a);
        b = get_parent(b);

        if(a > b){
            parent[a] = b;
        }else{
            parent[b] = a;
        }
    }
}