[코딩 테스트] 프로그래머스 - 섬 연결하기 (Lv.3) in Python

gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.htmln개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하라.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 본다.

예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능하다.

 

더 자세한 설명 - programmers.co.kr/learn/courses/30/lessons/42861

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

 

풀이

탐욕법 (Greedy method)을 이용하여 가중치가 할당된 간선으로 연결된 네트워크의 모든 정점을 최소 비용으로 연결하는 최적의 방법을 찾는 크루스칼 알고리즘 (Kruskal's Algorithm)의 대표격인 문제다!

 

각 섬들을 연결하는 방법 중, 간선에 할당된 숫자의 합이 최소인 경우를 찾는 것 - 알고리즘의 정의와 똑같은 문제이기 때문이다.

 

크루스칼 알고리즘을 더 잘 알기 위해서는, 다음의 강의를 완전 강력 추천한다!

프로그래머스 수업도 완벽하게 해내신 나동빈 강사님의 유투브 강의인데, 이해가 정말이지 쏙쏙된다.

www.youtube.com/watch?v=LQ3JHknGy8c

 

더 잘 이해하기 위해서, 위의 비디오에서 추천하는 17강 - Union-Find (합집합 찾기)도 듣는 것을 추천한다.

 

 

위의 비디오에서 보여주신 풀이 코드를 이번 문제와 합쳐, 아래처럼 solution을 구현한다.

 

 

코드 구현

# Union-Find Method
# get the  (smallest) parent node #
def getParent(parent, x):
    if parent[x] == x:
        return x
    return getParent(parent, parent[x])

# given two nodes to be connected, update their parents
def unionParent(parent, a, b):
    a = getParent(parent, a)
    b = getParent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# compare parent nodes of the given two nodes
# to see if they share the same parent - in this case, a cycle will be made
def compareParent(parent, a, b):
    a = getParent(parent, a)
    b = getParent(parent, b)
    if a == b:
        return True
    else:
        return False

# main function
def solution(n, costs):
    answer = 0
    count = 0
    
    # initialize parent-node table
    parent = [0] * n
    for i in range(n):
        parent[i] = i
    
    # sort the costs table per cost
    costs.sort(key = lambda x: x[2])

    # if a edge does not make a cycle, add
    for x in costs:
        if not compareParent(parent,x[0], x[1]):
            answer += x[2]
            unionParent(parent, x[0],x[1])
            count += 1

        # if # of edges = n - 1, it's the best
        if count == n - 1:
            break

    return answer

- 위의 세 함수는 Union-Find를 구현, solution 함수는 이를 이용해서 문제를 푸는 역할을 한다.

- 먼저 costs를 cost기준으로 오름차순으로 정렬하고,

- 각 노드의 parent를 저장해주는 list를 initialize한다.

- 각 노드의 기본 parent 값은 자기 자신이다.

- costs의 원소를 돌며, 해당 간선이 cycle을 만들지 않는다면

    - answer에 해당 간선의 cost를 더하고

    - 해당 간선을 '사용'하며 - unionParent사용

    - count의 값을 늘려준다.

- 최적의 경우, 간선의 개수는 (노드의 개수 - 1)과 같다. 따라서 count가 (n-1)과 같을 때, 루프를 break하자!

 

 

 

- Kruskal's Algorithm은 배워만 봤지 실제로 구현해서 문제에 쓰는 건 처음이었는데, 역시 아는 것이 답이다 싶다. 알고나니 문제 푸는 과정이 더 잘 보이고 재미있게 느껴지기 때문이다!