(Java)프로그래머스 코딩테스트 연습 - 탐욕법(Greedy) - 섬 연결하기

1. 문제

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

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

2. 나의 풀이

import java.util.*;

class Solution {
    public int solution(int n, int[][] costs) {
        int answer = 0;
        boolean [] check = new boolean [costs.length];
        ArrayList<Integer> visited = new ArrayList<>();
        for(int i = 1; i < n; i = i + 1) {
        	int cost = -1;
        	//System.out.println(i + "번째");
        	for(int j = 0; j < costs.length; j = j + 1) {
        		//System.out.println("확인할 costs : " + Arrays.toString(costs[j]));
        		if(check[j] == true) continue;
        		if(visited.size() == 0) {}
        		else if(!visited.contains(costs[j][0]) && !visited.contains(costs[j][1])) continue;
        		else if(visited.contains(costs[j][0]) && visited.contains(costs[j][1])) continue;
        		if(cost == -1) {
        			cost = j;
        		}else if(costs[cost][2] > costs[j][2]) {
        			cost = j;
        		}
        		//System.out.println(j + "번째에서 가장 적은 cost는 " + costs[cost][2]);
        	}
        	if(!visited.contains(costs[cost][0])) {
        		visited.add(costs[cost][0]);
        	}
        	if(!visited.contains(costs[cost][1])) {
        		visited.add(costs[cost][1]);
        	}
        	answer += costs[cost][2];
        	check[cost] = true;
        	//System.out.println("answer : " + answer);
        	//System.out.println("check : " + Arrays.toString(check));
        	//System.out.println("");
        }
        //System.out.println(visited);
        return answer;
    }
}

3. 다른 사람 풀이

import java.util.Arrays;

class Solution{
    public int solution(int n, int[][] costs){
        int sum = 0;
        int[] island = new int[n];

        for(int i = 0; i < n; i++)
            island[i] = i;

        Arrays.sort(costs, (a, b) -> Integer.compare(a[2], b[2]));

        for(int i = 0; i < costs.length; i++){
            if(find(island, costs[i][0]) != find(island, costs[i][1])){
                unite(island, costs[i][0], costs[i][1]);
                sum += costs[i][2];
            }
        }
        return sum;
    }

    private int find(int[] island, int x){
        if(island[x]== x)
            return x;
        return find(island, island[x]);
    }

    private void unite(int[] island, int x, int y){
        int a = find(island, x);
        int b = find(island, y);
        island[a] = b;
    }
}