[웅's 프로그래머스] 섬 연결하기 - 파이썬(Python) 풀이

문제를 읽자마자 아~ 이런 문제 어디서 많이 봤는데? 라는 생각이 들었다. 찾아보니 Kruskal 알고리즘의 대표적인 유형이었다.

 

나는 이 문제를 풀기 위해 3가지 개념을 공부했다.

1. Python 에서 list 를 정렬하는 방법

2. Union - Find 자료구조

3. Kruskal 알고리즘

---

1. Python 에서 list 를 정렬하는 방법

 

파이썬의 정렬에는 list.sort() 와 sorted(list) 두 가지 종류가 있다.

list.sort() 의 경우에는 list 를 정렬해 주지만, sorted(list) 의 경우에는 list 를 정렬한 것을 리턴해준다는 특징이 있다. sorted(list) 의 경우 list 자체에는 영향을 미치지 않는다.

 

또한 sort() or sorted() 에는 2가지 attribute 가 들어갈 수 있는데 

 - key = lambda 함수 : lambda 함수에서 정의 해주는 변수 순으로 정렬 가능

 - reverse = True ( 내림차순 ), False ( 오름차순 & 기본값 )

 

그냥 내가 참고한 블로그 링크를 올려 보겠다.

https://ooyoung.tistory.com/59

파이썬 정렬 함수 sort, sorted _ key = lambda, function / reverse= 파라미터 이용 방법 (Python)

---

2. Union - Find 자료구조는 집합의 특성 중에서도 조회와 합집합에 특화된(?) 자료구조이다.

S = { 1, 2, 3 }

T = { 2, 4, 5 }

 

조회 : 1∈S ?

합집합 : S U T = { 1, 3, 4, 5 }

 

이때 조회와 합집합 연산을 트리구조를 이용하여 O(logN) 시간 내에 하는 것이 특징이다.

역시나 공부하는데 큰 도움이 됐던 한국외대 신찬수 교수님의 영상을 링크로 남기겠다.

 

https://youtu.be/GaET9oHzC3Q

신찬수 교수님의 union-find 자료구조 명강의

---

3. Kruskal 알고리즘인데 중요한 포인트는 비용 순으로 오름차순 정렬 후

비용이 낮은 루트부터 검사해 나가며 비용과 연결된 노드가 같은 Tree 에 속하는 지 확인하는 과정이다. 

어려운 말인 것 같으니 역시나 명강의 신찬수 교수님의 강의 링크를 첨부하겠다.

https://youtu.be/bDbG2OJrY9s

신찬수 교수님의 Kruskal 알고리즘 명강의

위 세가지 개념을 토대로 Kruskal 알고리즘을 구현했는데, 코드는 아래와 같다.

 

def solution(n, costs):
    
    answer = 0

    def find(c):
        if par[c] == c:
            return c
        else:
            return find(par[c])

    def union(a, b):
        a, b = find(a), find(b)
        par[a] = b

    par = [i for i in range(n)]

    costs.sort(key = lambda x: x[2])
    for i in costs:
        if find(i[0]) != find(i[1]):
            answer += i[2]
            union(i[0], i[1])
        
    return answer