[그리디] 섬 연결하기 - Java코드 ★★★ (크루스칼, 신장트리)

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

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

 

문제

 

설계

일단 최속밧을 찾기위해서는 Costs로 오름차순 정렬은 필수이다.

Costs가 1이거나 작다고 해서 불필요하게 무작정 연결해서는 안된다.

모든섬 하나 이상의 선이 연결되어도 전체 통행에 대한 연결이 안됬을 수 있다.

선이 이어지는지 여부를 체크하기위한 부분이 필요하다.

 

이 문제는 신장 트리 구조를 알고 트루스칼 알고리즘을 사용해야하는 문제이다.

트루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하는 알고리즘이다.

 

연결해야 하는 노드수만큼의 배열을 만들어

배열의 index를 노드라 생각하고, 해당 노드의 값을 자기자신으로 초기화한 뒤,

마지막 leaf 노드까지 재귀적으로 순회하면서, 연결을 결정해주면 된다. 

 

 

풀이

import java.util.Arrays;
import java.util.Comparator;

class Solution {
	static int[] island;
	public static int findPoint(int a) {
		if(island[a] == a)
			return a;
		else
			return findPoint(island[a]);
	}
	public static int solution(int n, int[][] costs) {
		// costs 최솟값 정렬
		Arrays.sort(costs, new Comparator<int []>() {
			@Override
			public int compare(int o1[], int o2[]) {
				return o1[2] - o2[2];
			}
		});
		int ans=0;
		island = new int[n];
		for(int i=0;i<n;i++)	island[i]=i;
		for(int[] i : costs) {
			int a = findPoint(i[0]);
			int b = findPoint(i[1]);
			if(a != b) {	// 연결되어 있지 않으면
				ans+=i[2];
				island[a] = b;	// 신규 연결 , 기존의 연결선을 끊지않고, 연결해준다
               		// 이부분은 물리적 연결관계를 보장하지않고 논리적인 비용계산만 고려한것
			}
				
		}		
		return ans;
	}
}

 

포인트

객체에 대한 다양한 정렬이 불가피하니 Comparator를 잘 사용할줄 알아야한다.

노드의 갯수만큼 연결을 저장하는 배열을 전역적으로 사용하여 함수내에서 접근하도록 해주었다.

findPoint를 통해 해당 노드에서 연결되지 않은 노드의 끝지점을 가져온다.

a, b 두 노드의 끝이 다르다는건 연결되있지 않다는것,

같다는건 이미 연결되어 있다는 것이다.

 

 

중요한건 배열이 가지는 선은 하나이다.

이전에 연결을 끊으면서 신규연결정보를 저장해서는 안되기 때문에, 

연결선은 마지막 Leaf 값을 신규로 연결해주어야 한다. 

 

 

다른사람의 풀이

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;
    }
}

현재 제일 따봉을 많이 받은 풀이인데,

논리적인 설계가 거의 같다.

 

정렬에서 람다식을 사용했고, 연결관계를 정의할때 Unite 함수를 부르도록했는데

함수안에서  재귀호출이 많이 일어나는 find() 함수를 계속적으로 부르는 코드이다.

 

내 코드가 쬐금 더 효율적일 것 같다.