섬 연결하기(프로그래머스, Java)

문제링크: https://programmers.co.kr/learn/courses/30/lessons/42861

코딩테스트 연습 - 섬 연결하기 | 프로그래머스

알고리즘 설명:

가장 cost가 싼 간선으로 모든 노드를 연결하는 알고리즘이다.

• 양 방향으로 간선의 cost값을 알기 위해서 배열을 사용하여 두 방향 (A -> B, B -> A)의 cost를 넣어놓았다.

• 노드 0부터 탐색을 시작한다. 0부터 시작하므로 visited[0] = true

• 메서드 재귀호출하여 탐색한다.

• 재귀호출은 노드(섬)의 개수만큼 호출을 하고 변수 count를 만들어 재귀 호출한 횟수를 체크한다.

• 이중 for문으로 탐색한 노드의 간선에서 가장 작은 cost값을 가진 간선을 찾아 그 방향으로 탐색해 나아간다.

막혔던 지점:

DFS방식으로 낮은 값을 탐색할 수 있을 줄 알았지만 아니였다. 바로 프림 알고리즘을 사용.

 

package test;

public class ConnectionIsland {

    public static int solution(int n, int[][] costs) {
		boolean[]visited = new boolean[n];
		int answer = 0;

		int[][] nodeCost = new int[n][n];
		
		for(int i=0;i<costs.length;i++) {
			nodeCost[costs[i][0]][costs[i][1]] = costs[i][2];
			nodeCost[costs[i][1]][costs[i][0]] = costs[i][2];
		}
		
		visited[0] = true;
		answer = prim(nodeCost,visited,0,1);
		return answer;
		
		
	}
    
    public static int prim(int[][] nodeCost, boolean[] visited, int answer, int count) {
    	if(count == visited.length) return answer;
    	int minnode = -1;
    	int mincost =Integer.MAX_VALUE;
    	for(int i =0;i<visited.length;i++) {
    		if(visited[i]) {
    			for(int j=0;j<nodeCost.length;j++) {
    				if(!visited[j] && nodeCost[i][j] != 0 && mincost > nodeCost[i][j]) {
    					minnode= j;
    					mincost = nodeCost[i][j];
    				}
    			}
    		}
    	}
    	
    	visited[minnode] = true;
    	answer += mincost;
    	count++;
    	
    	return prim(nodeCost,visited,answer,count);
    }

	public static void main(String[] args) {
		int n = 4;
		int costs[][] = { { 0, 1, 1 }, { 0, 2, 2 }, { 1, 2, 5 }, { 1, 3, 1 }, { 2, 3, 8 } };
		System.out.println(solution(n, costs));

	}

}