프로그래머스 섬 연결하기

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

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

풀이 : 탐욕 알고리즘 / 프림 알고리즘 / 최소신장트리 찾기

 

참고 : 2021.09.20 - [알고리즘/알고리즘] - 탐욕 알고리즘 Greedy Algorithm

 

탐욕 알고리즘 Greedy Algorithm

class Solution {
    public int solution(int n, int[][] costs) {
            boolean[] isVisited = new boolean[n];
        int answer = 0;
        int visitedSpotCount = 0;
        int[][] graph = new int[n][n];
        isVisited[0] = true;

        for(int[] c : costs) {          
            graph[c[0]][c[1]]=c[2];
            graph[c[1]][c[0]]=c[2];
        }


        while(visitedSpotCount<n-1) {
            int minWeight   = Integer.MAX_VALUE;
            int visitedSpot = 0;
            for(int i=0; i<n; i++) {
                if(isVisited[i]) {
                    for(int j=0; j<n; j++) {
                        if(graph[i][j]>0 && !isVisited[j]) {
                            if(minWeight > graph[i][j]) {
                                minWeight = graph[i][j];
                                visitedSpot = j;
                            }
                        }
                    }
                }
            }

            visitedSpotCount++;
            answer += minWeight;
            isVisited[visitedSpot] = true;
        }

        return answer;
    }
}