프로그래머스 | LV.3 섬 연결하기 - 최소비용 신장 트리 (Java)

프로그래머스 | LV.3 섬 연결하기 - 최소비용 신장 트리

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

프로그래머스

 

임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.

• 이 부분을 잘 봤어야 한다.
• 즉, 시작점은 costs[i][0] 이 되고, 끝점은 costs[i][1] 이 되며, 비용가중치는 costs[i][2] 가 된다.

문제 설명

---

⬛첫 번째 풀이 

• union & find로 매번 연결하는 간선으로 사이클 형성 안되는지 확인하면서 간선을 연결해주어야 한다.
• 신장 트리는 간선의 개수가 (노드개수-1)이 최대이므로 while()문에 조건을 걸어주고, 연결할 최소 비용의 Edge가 사이클 형성하지 않는 선에서 가중치 누적 해준 뒤, 결합시키고 , useEdge++ 처리 해준다.

import java.util.*;

class Edge implements Comparable<Edge> {
    int s, e, val;
    Edge(int s, int e, int val){
        this.s = s;
        this.e = e;
        this.val = val;
    }
    @Override
    public int compareTo(Edge o){
        return this.val - o.val;//적은 가중치 우선 정렬 
    }
}
class Solution {
    static int[] parent;//부모 
    static PriorityQueue<Edge> pQ= new PriorityQueue<>();//기준 자동 정렬되도록 
    //find - 사이클 확인용 
    static int find(int a){
        if(a == parent[a]) return a;
        else{
            return parent[a] = find(parent[a]);
        }
    }
    //union - 결합용 
    static void union(int a, int b){
        a = find(a);
        b = find(b);
        if(a != b){
            parent[b] = a;//결합
        }
    }
    //솔루션 함수 
    public int solution(int n, int[][] costs) {
        
        parent = new int[n+1];//노드+1개수 
        for(int i=1; i<=n; i++){
            parent[i] = i;//자기 자신 초기화 
        }
        //데이터 입력받아서 가중치 적은 애 우선 정렬되게 큐에 담음 
        for(int i=0; i<costs.length; i++){
            int s= costs[i][0]; //시작점
            int e = costs[i][1];//끝점 
            int v = costs[i][2];//가중치 
            
            pQ.add(new Edge(s, e, v));
        }
        
        //여기서부터 최소스패닝트리 알고리즘
        int useEdge = 0;
        int answer = 0; //최소비용 누적용 
        while(useEdge < n-1){ //사용 엣지 개수 n-1개 되면 탈출 
            Edge cur = pQ.poll();//가장 가중치 작은 애 뽑기 
            if(find(cur.s) != find(cur.e)){ //두 정점 이어도 사이클 형성 안되면       
                union(cur.s, cur.e);//결합
                answer += cur.val; //가중치 누적 
                useEdge++;
            }
        }

        return answer;
    }
}

---

⬛두 번째 풀이  

- for(int[] i : costs) 로 하나씩 받아서 i[0], i[1], i[2] 각각 Edge에 매핑시켜 해결하는 방식도 존재 

import java.util.*;
class Edge implements Comparable<Edge> {
    int s, e, val;
    Edge(int s, int e, int val){
        this.s = s;
        this.e = e;
        this.val = val;
    }
    @Override
    public int compareTo(Edge o){
        //가중치 적은 애 기준 정렬 오름차순 
        return this.val - o.val;
    }
}
class Solution {
    static PriorityQueue<Edge> pQ = new PriorityQueue<>();
    static int parent[];
    
    //find
    static int find(int a){
        if(a == parent[a] ) return a;
        else{
            return parent[a] = find(parent[a]);
        }
    }
    
    //union
    static void union(int a, int b){
        a = find(a);
        b = find(b);
        if(a!=b){
        parent[b] = a;
        }
    }
    //솔루션 함수 
    public int solution(int n, int[][] costs) {
        parent = new int[n+1];
        for(int i=1; i<=n; i++) parent[i] = i;//자기 자신으로 초기화 
        
        //데이터 pQ에 삽입
        for(int[] i : costs){
            int a = i[0];
            int b = i[1];
            int val = i[2];
            pQ.add(new Edge(a, b, val));
        }
        
        //간선은 n-1개 연결해야 됨 
        int useEdge = 0;
        int answer = 0;
        
        while(useEdge < n-1){
            Edge cur = pQ.poll();
            if(find(cur.s) != find(cur.e)){
                union(cur.s, cur.e);
                answer += cur.val;
                useEdge++;
            }
        }
    
        return answer;
    }
}