섬 연결하기 (크루스칼 알고리즘)

문제

문제 링크

이 문제는 전형적인 크루스칼 알고리즘을 이용하는 문제로 보인다.

크루스칼 알고리즘이란
greedy algorithm을 이용하여 네트워크의 모든 정점을 최소 비용(MST)으로 연결하는 알고리즘


MST(최소 비용 신장 트리)
최소 비용의 간선으로 구성되었으며, 사이클이 없는 그래프를 의미한다.

---

나의 풀이

이 문제를 푸는데에 대략 3시간이 걸렸다.

문제의 방향은 맞았었다.


우선 최소비용 순으로 정렬 후, 하나씩 선택해 나가다가 cycle이 생길 때는 선택하지 않는 방식으로 해결하면 될 것이라고 생각했다.


오래 걸린 이유는 dfs를 통해 cycle을 판별 할 수 있을 것이라 생각했기 때문이다.


(나중에 알고보니 dfs를 통해 cycle 존재를 판별할 수 있는 것은 맞지만 '재귀적으로' 하는 것이 아니라 stack을 통해 구현했을 때, 가능하다고 한다.)


문제를 풀다가 dfs를 이용해서 아직 내 능력으로 해결할 수 없을 것 같았고,
따라서, graph에서 cycle의 존재 여부를 판단하는 방법을 찾아보았다.


그래서 union&find라는 방법을 알게 되었고 적용해 보았다. (👉 : union&find를 찾은 곳)

나는

1) value를 이용하여

2) 현재 선택한 node의 value 중 작은 것과 큰 것을 분류하고

3) 큰 값을 작은 값으로 대체하는 방법으로
union&find를 시행해 나갔다.

# 1. costs를 비용을 이용하여 오름차순 정렬.
# 2. 하나씩 선택하면서,
#  2-1. cycle이 존재하면 탈락
#  2-2. cycle이 존재하지 않으면 선택
# 3. 선택한 경로가 node -1 개면 함수 종료.
#------------------------------------------------
## <cycle존재 여부 확인법>
## 1. 집합 이용 -> 코드가 너무 길어질 가능성 존재함.(집합끼리 합쳐야하는 상황에서)
## ---> union&find 알고리즘으로 가능하다고 함.....
## 2. dfs 이용 -> 연결 matrix를 생성해야해서 공간복잡도가 늘어날 것으로 예상되지만 집합보다 연산이 적을듯..?  (dfs로 구현하려다가 실패하였음)
##
from collections import defaultdict
def solution(n, costs):
    #내림차순으로 costs 정리 (오른쪽 값이 가장 작음)
    answer = []
    descCosts = sorted(costs,key = lambda x:x[2],reverse = True)
    
    sets = defaultdict(int)
    
    for cost1,cost2,_ in costs :
        if not sets[cost1]:
            sets[cost1] = cost1
        if not sets[cost2]:
            sets[cost2] = cost2
            
    while len(answer) < n-1:
        
        least = descCosts.pop()
        #least의 0,1 idx를 key로 사용하여, 
        #value가 큰 것을 big, 작은 것을 sml이라고 칭하였음
        
        big,sml = max(sets[least[0]],sets[least[1]]), min(sets[least[0]],sets[least[1]])
        
        #둘이 같지 않으면 다른 네트워크 상에 있다는 듯임.
        if big != sml:
            answer.append(least[2])
            for key,value in sets.items():
                if value == big:
                    sets[key] = sml
                    
                    
            
            
    return sum(answer)

---

다른 사람의 풀이

이 사람은 union&find를 재귀적으로 구현하였다.
너무도 아름다워 기록하고 싶었기에 가져왔다.
다만 ancestor 함수를 따라가보자면, 문제에서 cost들이 모두 cost[1]이 [0]에 비해 크기 때문에 가능했던 것으로 보인다.

def ancestor(node, parents):
    if parents[node] == node:
        return node
    else:
        return ancestor(parents[node], parents)

def solution(n, costs):
    answer = 0
    edges = sorted([(x[2], x[0], x[1]) for x in costs])
    parents = [i for i in range(n)]
    bridges = 0
    for w, f, t in edges:
        if ancestor(f, parents) != ancestor(t, parents):
            answer += w
            parents[ancestor(f, parents)] = t
            bridges += 1
        if bridges == n - 1:
            break
    return answer