[프로그래머스]섬 연결하기

https://school.programmers.co.kr/learn/courses/30/lessons/42861#

프로그래머스

풀이

그리디 문제라고 풀다가 그래프 문제가 나오길래 크루스칼 알고리즘은 그리디 알고리즘의 일종이라는 점을 깜빡했다. 오랜만에 서로소 집합 문제여서 동빈나 센세의 강의도 찾아보고 풀었다. 서로소 집합 문제는 부모를 찾는 함수(find_parent)와 부모를 합치는 함수(union_parent)로 나눌 수 있는데, 이 문제 같은 경우에는 싸이클이 발생하지 않는 경우에 한해서(두 섬에 대하여 통하는 길이 두 개일 이유가 없다) 비용이 적은 간선부터 처리하면서 노드들을 이어주면 된다. 여기서 크루스칼 알고리즘을 사용하려면 방향이 없는(문제에서 a와 b로 이어진 간선과 b와 a로 이어진 간선은 같은 간선이라고 하였고, 이어지는데에 방향의 의미를 가지지 않는다) 그래프 문제여야만 풀 수 있다.

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]
def union_parent(parent, x, y):
    a = find_parent(parent, x)
    b = find_parent(parent, y)
    if a < b:
        parent[b] = parent[a]
    else:
        parent[a] = parent[b]
def solution(n, costs):
    answer = 0
    v = len(costs)
    parent = [0 for _ in range(n)]
    for i in range(n):
        parent[i] = i
    costs.sort(key = lambda x: x[2])
    for c in costs:
        a, b, cost = c
        if find_parent(parent, a) != find_parent(parent, b):
            union_parent(parent, a, b)
            answer += cost
    return answer