[프로그래머스] 섬 연결하기 - java

문제 설명 :

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

프로그래머스

 

문제 요약 :

1. 최소 신장 트리 구하기

 

문제 풀이 시간 : 20분

문제 성공 여부 : 성공

 

접근 방법(성공) :

1. 크루스칼 알고리즘을 사용하여 모든 간선을 pq에 저장
2. pq에서 가장 작은 가중치의 사이클 유무를 확인 및 추가

출처: 프로그래머스 섬 연결하기 예시 그림

이처럼 정점과 가중치가 있는 간선들이 주어질 때, 최소 신장트리를 구하기 위해서 크루스칼과 프림 알고리즘을 사용할 수 있다.

 

제한사항이 여유로웠기에 둘 중 하나를 선택해서 사용하면 되었고, 가장 손에 익은 크루스칼 알고리즘을 사용하였다.

 

모든 간선을 우선순위 큐에 넣은 뒤 작은 간선 부터 꺼내서 from과 to 정점의 사이클을 Union Find를 활용하여 확인했다.

 	while(!pq.isEmpty()){
            Node cur = pq.poll();
            int x = cur.x;
            int y = cur.y;
            int val = cur.val;
            
            if(isUnion(x,y)) continue; // 사이클이 생기는 경우 continue;
            
            makeUnion(x,y); // 사이클이 없는 경우 Union 시키고 ans에 가중치 추가
            ans+=val;
        }

 

유니온 파인드는 union인지 확인하는 isUnion 함수, parent를 찾는 find 함수, 부모를 같게 하는 makeUnion 함수로 구현했다.

    boolean isUnion(int x, int y){
        int xx = find(x); // 부모 찾기
        int yy = find(y); // 부모 찾기
        
        if(xx != yy) return false; // 부모가 다를 경우 false
        return true;
    }
    
    int find(int x){
        if(parents[x] == x) return x; // parent가 본인일 경우 반환
        return parents[x] = find(parents[x]); // 부모 찾기
    }
    
    void makeUnion(int x, int y){
        int xx = find(x);
        int yy = find(y);
        
        parents[xx] = yy; // x를 부모로 union하기
        return;
    }

 

 

 

 

전체 코드(성공) :

import java.util.*;
class Solution {
    static class Node implements Comparable<Node>{
        int x, y, val;
        Node(int x, int y, int val){
            this.x = x;
            this.y = y;
            this.val = val;
        }
        
        @Override
        public int compareTo(Node n){
            return this.val - n.val;
        }
    }
    
    static int[] parents;
    public int solution(int n, int[][] costs) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        for(int i = 0; i<costs.length; i++){
            pq.add(new Node(costs[i][0], costs[i][1], costs[i][2]));
        }
        
        parents = new int[n];
        for(int i=0; i<n; i++) parents[i] = i;
        
        int ans = 0;
        while(!pq.isEmpty()){
            Node cur = pq.poll();
            int x = cur.x;
            int y = cur.y;
            int val = cur.val;
            
            if(isUnion(x,y)) continue;
            
            makeUnion(x,y);
            ans+=val;
        }
        return ans;
    }
    
    boolean isUnion(int x, int y){
        int xx = find(x);
        int yy = find(y);
        
        if(xx != yy) return false;
        return true;
    }
    
    int find(int x){
        if(parents[x] == x) return x;
        return parents[x] = find(parents[x]);
    }
    
    void makeUnion(int x, int y){
        int xx = find(x);
        int yy = find(y);
        
        parents[xx] = yy;
        return;
    }
}