[프로그래머스] 탐욕 알고리즘 - 섬 연결하기

문제를 읽고 최소 스패닝 트리를 만드는 문제라는 것을 알았고

크루스칼 알고리즘을 이용하였다.

 

	static int solution(int n, int[][] costs) {
        int answer = 0;
        
        ArrayList<Integer> in=new ArrayList<>();
        int[][] adj = new int[n][n];	//인접한 섬들을 알려주는 배열, 0으로 초기화 상태
        
        for(int i = 0; i < costs.length; i++) {
        	//선은 양방향
            adj[costs[i][0]][costs[i][1]] = adj[costs[i][1]][costs[i][0]] = costs[i][2];
        }
        
        in.add(0);
        
        while(in.size()<n) {
        	int min=Integer.MAX_VALUE;
        	int minIdx=-1;
        	for(int i=0;i<in.size();i++) {      
        		int island=in.get(i);
        		for(int j=0;j<n;j++) {
        			// 연결할 섬이 in에 포함되어 있지 않고, 현재 island와 j가 연결됨(0이상 값), 중 가장 작은 값  
        			if(!in.contains(j) && adj[island][j]>0 && adj[island][j]<min) {
        				min=adj[island][j];
        				minIdx=j;
        			}
        		}
        	}
        	in.add(minIdx);	//섬 포함하기 (연결할 섬 = minIdx)
        	answer+=min;// 정답에 가중치 합하기
        }
        
        return answer;
    }

 

포함되어있는 섬들과 포함되어있지 않은 섬들로 나누어 주어

초기 0 섬을 포함시킨 후, 0과 연결된 섬 중 가장 가중치가 작은 섬을 포함한다.

모든 섬이 포함될 때까지 반복한다.