(코테) 프로그래머스_섬 연결하기 *유니온 파인드

문제 링크

 

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

 

 

 

 

 

import java.util.*;
class Solution {
    public int solution(int n, int[][] costs) {
        int answer = 0;
        Arrays.sort(costs, (a,b)-> a[2] - b[2]);   
        
        
        int[] parent =new int[n];
        int count=0;
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }

        
        for(int[] list:costs){
            int to =list[0];
            int from =list[1];
            int cost =list[2];
        
            //그룹이 다르면 신규임
            if(find(parent,to) != find(parent,from)){
                union(parent,to,from);
                answer+= cost;                
                count++;
                //if(count>=n) break;
                if (count == n - 1) break;
            }            
            
        }     
        
        
        return answer;
    }
    
    public int find(int[] parent , int cild){        
        if(parent[cild]==cild) return cild;
        else return parent[cild] = find(parent,parent[cild]);
    }
    
    public void union(int[] parent , int a ,int b){    
        int to = find(parent,a);
        int from = find(parent,b);
        
        if(to<from) parent[from] = to;
          else  parent[to] = from;                   
        
    }
    
}

 

 

실수한 부분

1. int[] parent = new int[n]; 

int배열 선언후 초기값 선정 안했음. 그러므로 다 0이라 

인덱스 값이 자기 자신인게 root인데 그걸 못참음.

->

for (int i = 0; i < n; i++) {
    parent[i] = i;
}

 

 

2. 종료 조건 (count >= n) 으로 적음.  

종료 조건이 (count >= n) 인 경우는 오지 않음. 

그래서 for문은 break; 문에 걸리지 않아 비효율적

 

 

-> 올바른 답 -if (count == n - 1) break;

n-1 마지막 인덱스임.

 

3. find() 함수에    부모값으 변수값을 갱신 안해줌 find(parent, parent[child]);  // path compression

자기 바로 윗 부모로만 되어있고, 가장 조상 부모를 저장해두면 다음면 find에서는 find재귀가 여러번 안타서 

바로 root부모를 반환해 효율적임.

->  parent[cild] = find(parent,parent[cild]);