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

vagabondms·2021년 3월 12일
0

오답노트 Lv.3

목록 보기
1/2

문제

문제 링크

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

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


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

나의 풀이

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

문제의 방향은 맞았었다.


우선 최소비용 순으로 정렬 후, 하나씩 선택해 나가다가 cycle이 생길 때는 선택하지 않는 방식으로 해결하면 될 것이라고 생각했다.
오래 걸린 이유는 dfs를 통해 cycle을 판별 할 수 있을 것이라 생각했기 때문이다.
(나중에 알고보니 dfs를 통해 cycle 존재를 판별할 수 있는 것은 맞지만 '재귀적으로' 하는 것이 아니라 stack을 통해 구현했을 때, 가능하다고 한다.)
문제를 풀다가 dfs를 이용해서 아직 내 능력으로 해결할 수 없을 것 같았고, 따라서, graph에서 cycle의 존재 여부를 판단하는 방법을 찾아보았다.
그래서 __union&find__라는 방법을 알게 되었고 적용해 보았다. (👉 : [union&find를 찾은 곳](https://chanhuiseok.github.io/posts/algo-33/))

__나는 __

  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

관심 있을 만한 포스트

0개의 댓글