[python3] 프로그래머스 섬 연결하기 ( 그리디, MST, 크루스칼, 유니온 파인드)

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.
다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

처음에는 그래프 알고리즘을 고민했다. 다익스트라,플로이드를 떠올렸지만 이건 목적지가 존재하는 경우에 사용하는 알고리즘이라 사용불가능 했다. 그러다가 가중치를 기준으로 정렬하여 하나씩 포함하면 되지 않을까 했고 visited 배열을 만들어 노드를 체크해주었다. 

def solution(n, costs):
    answer = 0
    costs.sort(key=lambda x: (x[2]))
    print(costs)

    parent = [i for i in range(n)]
    for info in costs:
        A, B, C = info
        if parent[A] != parent[B]:  # 다른 부모라면 ㄱㅊ
            if parent[A] < parent[B]:
                parent[A] = parent[B]
            else:
                parent[B] = parent[A]
            answer += C
    return answer

그러나 왜그런지 모르겠지만 동작을 제대로 하지 않았다. 그래서 찾던중 MST의 크루스칼 알고리즘을 써야 한다는 것을 알게 되었다.

MST는 Minimum Spanning Tree의 약자로 span이란 기간을 의미해서 직역하면 최소화된 기간 트리이다. 좀 더 풀어 말하면 트리가 낮은 가중치로 연결되어 있다고 볼 수 있다. 다르게는 그래프의 최소 연결 부분 그래프 라고 할 수 있다.
이러한 MST를 구현하기 위해서는 크루스칼 알고리즘과 프림 알고리즘이 존재한다.

크루스칼 알고리즘은 아래와 같은 단계로 진행한다.

1. 코스트(간선의 가중치 혹은 거리)별로 정렬한다.(오름차순)
2. 하나씩 꺼내서 각 정점이 서로 같은 그룹에 속하는지 판별한다. (파인드 함수 사용)
   2-1. 다른 정점에 속하는 경우 같은 그룹으로 묶어준다. (유니온 함수 사용)
   2-2. 같은 정점에 속하는 경우 연산을 진행하지 않는다.
3. 2단계를 반복하며 모든 간선을 체크한다

이렇게 진행하면 된다. 그럼 코드는 아래와 같다.

"""
MST : 그래프를 최소의 비용으로 연결하는 최적의 해답
1. 크루스칼
    정렬후에 유니온 파인드를 이용하여 사이클이 생기지 않도록 연결하는 방법
2. 프림
"""


def find(parent, node):  # 루트 노드를 찾아준다.
    if parent[node] == node:  # 자신의 값을 가지면 지가 루트임
        return node
    parent[node] = find(parent, parent[node])  # 부모노드를 기준으로 모든 노드의 부모를 루트로 바꾼다.
    return parent[node]


def union(parent, a, b):  # 두 노드를 합친다.

    a = find(parent, a)  # 루트 노드를 알아온다.
    b = find(parent, b)

    if a == b:  # 같은 그룹인지 검증
        return False

    if a <= b:
        parent[b] = a # 루트 노드의 부모에 새로운 루트 노드로 갱신
    else:
        parent[a] = b # 루트 노드의 부모에 새로운 루트 노드로 갱신
    return True


def solution(n, costs):
    answer = 0
    costs.sort(key=lambda x: (x[2]))

    parent = [i for i in range(n)]
    for info in costs:
        A, B, C = info
        if union(parent, A, B):  # 다른 부모라면 ㄱㅊ
            answer += C
    return answer