100일 동안 매일 알고리즘을 하면? - 14일차

100일 동안 매일 알고리즘을 하면? - 14일차

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

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

 

이 문제는 크루스칼(Kruskal) 알고리즘으로 풀 수 있는 문제이다.

크루스칼 알고리즘을 이해하기 위해서 2가지 배경지식이 필요한데, 첫번째는 spanning tree 이고, 두번째는 union-find 이다.

 

1. spanning tree 란?

spanning tree 는 n 개의 정점을 (n-1) 개의 간선을 사용해서 모두 연결하는 트리이다.

여러 spanning tree 중, 모든 간선의 비용 합이 가장 작은 spanning tree 를 (MST: minimun spanning tree) 라고 부른다.

크루스칼 알고리즘은 이 MST 를 구하는 알고리즘이다.

 

2. union-find 란?

union-find 를 이해하기 위해선 먼저 서로소 집합을 알아야 한다.

서로소 집합이란, 말그대로 두 집합의 교집합이 공집합인 집합이다. 

서로소 집합을 조금 확장한게 서로소 트리이다.

우리는 서로소 트리를 이용해서 그래프에서 싸이클이 생성되었는지 알 수 있다.

예를들어 x1 과 x2 를 연결하는 간선을 만들려고 할때, 이 간선이 싸이클을 형성하는지 알고싶다.

그럼, 특정 x1, x2 각각의 서로소트리 최상단 부모의 값을  비교함으로서,  두 부모가 같으면, 해당 간선은 싸이클을 형성하고, 그렇지 않으면 싸이클을 형성하지 않는다는 것을 알 수 있다.

 

union 은 두 서로소 집합을 합치는 함수이고, find 는 최상단 부모 노드를 리턴하는 함수이다.

 

 

3. 크루스칼 알고리즘 사용법

크루스칼 알고리즘은 MST 를 만드는 알고리즘이며, MST 를 만들기 위한 조건이 2가지 있다.

첫번째는 MST 가 n 개의 노드를 가진다고 가정했을때 n-1 개의 간선으로 구성되어 있어야하고, 

두번째는, 싸이클을 형성하면 안된다.

 

먼저, 비용을 기준으로 오름차순으로 정렬한다.

그 다음, 간선을 1개씩 pick 하면서, 해당 간선이 싸이클을 형성하지 않으면, answer 에 비용을 추가한다.

만약 싸이클을 형성하면 answer에 비용을 추가하지 않고 넘어간다.

총 n - 1 개를 Pick 했으면 answer 를 리턴한다.

 

 

4. 소스코드

def solution(n, costs):
    costs.sort(key=lambda x: x[2]);
    count = n - 1;
    answer = 0;
    roots = [0] * n;
    for i in range(n):
        roots[i] = i;
    
    
    def find(node, roots):
        if (node == roots[node]):
            return node;
        else:
            return find(roots[node], roots);
    
    def union(parentNode, childNode, roots):
        x = find(parentNode, roots);
        y = find(childNode, roots);
        
        roots[y] = x;
    
    for cost in costs:
        node1 = cost[0];
        node2 = cost[1];
        value = cost[2];
        
        if (find(node1, roots) == find(node2, roots)):
            continue;
        else:
            answer += value;
            union(node1, node2, roots);
            count -= 1;
        
        if (count == 0):
            break
    return answer;