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

1. 소요시간 : 20분
2. 문제 사이트 : 프로그래머스
3. 문제 수준 : 레벨 3
4. 문제 유형 : 그래프이론 , 그리디 알고리즘
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
7. 문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42861
8. 푼 날짜 : 2023.03.07

1. 사용한 자료구조 & 알고리즘

-크루스칼 알고리즘

문제를 보면 최소 스패닝 트리의 문제라는 것을 곧바로 알 수 있다. 크루스칼 알고리즘을 이해하기 위해서는 유니온 & 파인드 (Union & Find ) 개념을 먼저 알고 있어야 한다. 크루스칼 알고리즘은 최소의 비용으로 모든 정점을 연결시키는 알고리즘이다.

2. 풀이과정

1. 자료들을 비용이 작은 순서대로 정렬한다.
2. 두 정점이 연결되어 있는지를 확인한다. union & find의 find 를 사용해서 node1 과 node2가 서로 연결되어 있나 확인한다.
3. find 한 부모가 서로 다르면 union 한다.
4. union 할 때마다 그 비용을 더해준 뒤 최종적으로 출력한다.

3. 소스코드

import java.util.*;
class Solution {
    static int parent[];
    public int solution(int n, int[][] costs) {
        
        parent=new int[n+1];
        for(int i=1;i<parent.length;i++)
            parent[i]=i;
      
        Arrays.sort(costs,new Comparator<>(){
            @Override
            public int compare(int n1[],int n2[]){
                if(n1[2]>n2[2])
                    return 1;
                return -1;
            }
         });
        int totalCost=0;
        for(int i=0;i<costs.length;i++){
            int node1=costs[i][0];
            int node2=costs[i][1];
            int cost = costs[i][2];
            if(find(node1)!=find(node2)){
                union(node1,node2);
                totalCost+=cost;
            }
        }
        
        return totalCost;
    }
    public static void union(int node1,int node2){
        node1=find(node1);
        node2=find(node2);
        if(node1>node2)
            parent[node1]=node2;
        else
            parent[node2]=node1;
    }
    public static int find(int node){
        if(parent[node]==node)
            return node;
        
        return find(parent[node]);
    }
}

4. 결과

5. 회고

다른 사람의 풀이를 봤는데 전체적으로 코드는 나와 비슷하나 최소 스패닝 트리의 특징을 하나 망각한 것이 있었다. 바로 간선의 개수가 n-1 개 라는 것이다. 즉, 노드의 개수가 5개라면 간선이 최대 4개 까지 나올수 있다는 사실이다. 내 코드에서는 union 해줄 때마다 count 를 세어주고, count가 n-1 개라면 중간에 break 하는 코드가 추가적으로 필요해 보인다. 모든 정점이 Union 한 뒤에도 불필요하게 계속해서 다음 간선을 확인하고 있기 때문이다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고 있다.
https://solved.ac/profile/anwlro0212