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

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

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

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
		class Node{
			int end, cost;
			public Node(int end, int cost) {
				this.end = end;
				this.cost = cost;
			}
		}
		List<Node> list[];
	    public int solution(int n, int[][] costs) {
	        int answer = 0;
	        
	        int [] minEdge = new int[n];
	        boolean [] visited= new boolean[n];
	        Arrays.fill(minEdge, Integer.MAX_VALUE);
	        list=new List[n];
	        
	        for(int i=0; i<n; i++) {
	        	list[i]=new ArrayList<>();
	        }
	        
	        for(int i=0; i<costs.length; i++) {
	        	list[costs[i][0]].add(new Node(costs[i][1],costs[i][2]));
	        	list[costs[i][1]].add(new Node(costs[i][0],costs[i][2]));
	        }
	        
	        minEdge[0]=0;
	        
	        int vertex=0;
	        int min=Integer.MAX_VALUE;
	        
	        
	        for(int k=0; k<n; k++) {
	        	min=Integer.MAX_VALUE;
	        	for(int i=0; i<n; i++) {
	        		if(!visited[i] && min>minEdge[i]) {
	        			vertex=i;
	        			min=minEdge[i];
	        		}
	        	}
	        	answer+=min;
	        	visited[vertex]=true;
	        	for(int i=0; i<list[vertex].size(); i++) {
	        		int end=list[vertex].get(i).end;
	        		int cost= list[vertex].get(i).cost;
	        		if(!visited[end] &&
	        			minEdge[end]> cost)
	        				minEdge[end]=cost;
	        	}
	        }
	        return answer;
	    }
	}

소요시간 : 30분

 

MST문제 입니다.... 따로 예외사항도 없고...크루스칼 보다는 프림알고리즘이 조금더 효율적이라고 생각해서 프림알고리즘으로 풀었습니다.