[프로그래머스] 섬 연결하기(Java - 탐욕법[Greedy])

문제설명

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

제한사항

• 섬의 개수 n은 1 이상 100 이하입니다.
• costs의 길이는 ((n-1) * n) / 2이하입니다.
• 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
• 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

전체코드(Java)

import java.util.*;

class Solution {
    public int solution(int n, int[][] costs) {
        // 섬과 섬이 연결된 상태를 저장
        int[][] connect = new int[n][n];
        // 섬의 개수와 연결된 개수 선언
        int answer = 0,connection = 0,island = 0;
        // 건설비용이 낮은 순서대로 경로를 정렬한다.
        Arrays.sort(costs, (c1,c2) -> c1[2] > c2[2] ? 1 : -1 );
        
        // 다리를 순회하면서 하나씩 연결해보고 만일 연결된 개수가 증가증가하지 않으면 연결을 해제한다.
        for(int[] c : costs){
            connect[c[0]][c[1]] = c[0]+1;
            connect[c[1]][c[0]] = c[1]+1;
            connection = countConnection(connect);
            if(island>=connection){
                connect[c[0]][c[1]] = 0;
                connect[c[1]][c[0]] = 0;
            }else{
                island = connection;
                answer += c[2];
            }
        }
        
        return answer;
    }
    
    public int countConnection(int[][] connect){
        
        int count = 0;
        
        Queue<Integer> queue = new LinkedList<>();
        int[] visit = new int[connect.length];
        // 섬과 섬이 연결된 개수를 파악한다.
        for(int loop=0;loop<connect.length;loop++){
            queue.add(loop);
            visit[loop] = 1;
            while(!queue.isEmpty()){
                int island = queue.poll();
                for(int i=0;i<connect.length;i++){
                    if(connect[island][i]!=0 && visit[i]!=1){
                        queue.add(i);
                        visit[i] = 1;
                        count+=1;
                    }
                }    
            }
        }
        return count;
    }
}

[ 참고 ]

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