[JAVA] 탐욕법(Greedy) "섬 연결하기"

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

 

• (크루스칼알고리즘)주어진 모든 간선을 비용을 기준으로 오름차순 정렬한다.(PriorityQueue사용)
• 간선의 부모 노드를 기록한다.
• 싸이클이 만들어지지 않게 부모노드를 체크하며 간선을 연결한다.

=> Union 알고리즘을 이용한다!

초록색 선으로 이어진 비용들의 합을 리턴한다.

 

import java.util.*;

class Solution {
    class Edge implements Comparable<Edge> {
        int from, to, cost;

        Edge(int from, int to, int cost){//간선문제는 from to를 만들어주는것이 좋다.
            this.from = from;
            this.to = to;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge o){
            return this.cost - o.cost;
        }
    }

    static int[] parent;
    static PriorityQueue<Edge> pq;

    public int solution(int n, int[][] costs) {
        int answer = 0;
        parent = new int[n];
        pq = new PriorityQueue<>();

        for(int i = 0 ; i < costs.length ; ++i){
            Edge edge = new Edge(costs[i][0], costs[i][1], costs[i][2]);
            pq.offer(edge);
        }

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

        while(!pq.isEmpty()) {
            Edge edge = pq.poll();

            if(find(edge.from) == find(edge.to)) {
                System.out.println(edge.from+"-"+edge.to + "패스");
                continue;
            }
            else {
                union(edge.from, edge.to);//유니온 알고리즘이 중요.
                answer += edge.cost;
            }
        }

        return answer;
    }

    public int find(int n){
        if(parent[n] == n) return n;
        return parent[n] = find(parent[n]);//재귀로 부모노드를 찾는 메소드
    }
    public void union(int a, int b){
        System.out.print("("+a+","+b+")");
        int rootA = find(a);
        int rootB = find(b);

        if(rootA != rootB) {
            parent[rootB] = rootA;
            System.out.println("rootB가 rootA로 변경:" +parent[rootB]);
        }
    }
}

velog.io/@hyeon930/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%84%AC-%EC%97%B0%EA%B2%B0%ED%95%98%EA%B8%B0-Java

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

parent[]배열은 각 노드에 대하여 부모를 계속해서 업데이트한 값을 넣어준다.

 

if문에서는 엣지(간선)의 from, to부분 모두 한 부모노드에 귀속되어있으면 값이 같다.

else문에서는 엣지간의 결합이 이어진다.