프로그래머스 Lv.3) 섬 연결하기

고득점 Kit - Greedy(탐욕법)

섬 연결하기

코딩테스트 연습 - 섬 연결하기

 

풀이

 

find - union가 부족하다고 판단되서, 다시 감을 잡고자 다시 풀었다.

풀이 방법은 처음 풀었을 때와 크게 차이점이 없었고, find 메소드와 union메소드만 잘 짜준다면 find - union문제는 무리 없이 풀 수 있을 것 같다.

 

로직

 

1. parents 배열을 선언 및 초기화한다.

2. 두 섬의 번호와 비용을 담을 class Island 를 선언한다.

3. 주어진 연결 정보를 담은 배열을 순회하면서, Island 변수를 만들어 우선순위 큐에 담아준다. ( 비용 오름차순 정렬)

4. Queue에서 정보를 빼와서, 부모가 같은지 여부에 따라 union 및 비용을 더해준다.

 

코드 1

 

import java.util.PriorityQueue;

class Solution {
    public static int[] parent;
    public static PriorityQueue<Island> islandPQ;

    private static void union(int x, int y) {
        x = find(x);
        y = find(y);
        if(x != y) {
            parent[y] = x;
        }
    }

    public static int find(int x) {
        if(parent[x] == x) {
            return x;
        }

        return parent[x] = find(parent[x]);
    }
    public static boolean isSameParent(int x, int y) {
        return find(x) == find(y) ? true : false;
    }

    private static int[] inItParent(int n) {
        int[] result = new int[n];

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

        return result;
    }
    
    public int solution(int n, int[][] costs) {
        int answer = 0;
        islandPQ = new PriorityQueue<>();
        parent = inItParent(n);

        for(int[] info : costs) {
            islandPQ.add(new Island(info[0], info[1], info[2]));
        }


        while(!islandPQ.isEmpty()) {
            Island island = islandPQ.poll();

            if(!isSameParent(island.origin, island.target)) {
                answer += island.cost;
                union(island.origin, island.target);
            }
        }

        return answer;
    }
}

class Island implements Comparable<Island> {
    int origin;
    int target;
    int cost;

    public Island(int origin, int target, int cost) {
        this.origin = origin;
        this.target = target;
        this.cost = cost;
    }

    @Override
    public int compareTo(Island island) {
        if(this.cost < island.cost) {
            return -1;
        } else if( this.cost == island.cost) {
            return 0;
        } else {
            return 1;
        }
    }
}

 

코드 2

 

import java.util.PriorityQueue;

class Solution {
    int[] parents;
    public int solution(int n, int[][] costs) {
        int answer = 0;
        inItParents(n);
        PriorityQueue<Node> pq = getOrderQ(costs);
        
        while(!pq.isEmpty()) {
            Node node = pq.poll();
            find(node.left); // 왜 널포인터
            if(find(node.left) != find(node.right)) {
                union(node.left,node.right);
                answer += node.cost;
            }
        }
        
        return answer;
    }
    
    private void inItParents(int n) {
        parents = new int[n];
        for(int i=0; i<n; i++) {
            parents[i]=i;
        }
    }
    
    private PriorityQueue<Node> getOrderQ(int[][] costs) {
        PriorityQueue<Node> result = new PriorityQueue<>();
        for(int[] info : costs) { 
            result.offer(new Node(info[0],info[1],info[2]));
        }
        return result;
    }
    private int find(int x) {
        if(x == parents[x]) {
            return x;
        }
        return parents[x] = find(parents[x]);
    }
    
    private void union(int val1, int val2) {
        val1 = find(val1);
        val2 = find(val2);
        if(val1 != val2)  {
            parents[val2] = val1;
        }
    }
}

class Node implements Comparable<Node>{
    int left;
    int right;
    int cost;
    
    public Node(int left, int right, int cost) {
        this.left = left;
        this.right = right;
        this.cost = cost;
    }
    
    @Override
    public int compareTo(Node n) {
        return this.cost > n.cost ? 1 : -1;
    }
}