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

문제 풀이

분류는 그리디로 되어있으나 풀이는 크루스칼로 푼 문제입니다.

그래프가 아니라 단순 노드 연결만 해도 쉽게 풀리는데 일부로 재활 겸 MST로 접근하였습니다.

다익스트라와 크루스칼 둘 다 가능한 문제지만 오히려 다익스트라보다 크루스칼이 가물가물 해서 복기 겸 크루스칼로 풀었습니다.

크루스칼의 핵심은 정렬과 유니온 파인드인데 정렬 때문에라도 그리디라고 할 수 있겠네요.

1. costs를 비용 순서대로 정렬하기
2. parents를 만들어서 각 섬이 연결되어 있는지 확인 준비 (연결할 수 없는 섬은 주어지지 않기에 사실 필요 없긴 합니다만..)
3. costs를 순회하며 find와 union을 확인하기.
   연결되어 있는 상태라면 넘어가고 연결되어 있지 않는다면 answer에 추가해 줍니다.
   비용 순으로 정렬하였기에 최소 비용은 보장되기에 따로 확인할 필요가 없습니다.
4. 모든 섬들을 확인했으면 종료

풀이 코드

def solution(n, costs):
    answer = 0
    island = sorted(costs, key=lambda x: x[2])
    parents = [i for i in range(n)]
    cnt = 0

    def find(x):
        if x == parents[x]:
            return x

        parents[x] = find(parents[x])  # 경로압축, 같은 그룹이면 쳐낼거니까
        return parents[x]

    def union(x, y):
        rootx = find(x)
        rooty = find(y)

        if rooty == rootx:  # 같은 그룹이면 암것도 안함. 사이클이니까 터트려
            return

        if rootx < rooty:
            parents[rooty] = rootx
        else:
            parents[rootx] = rooty

    for start, end, cost in island:
        # 연결이 되지 않은 상태라면 연결하고 비용 추가
        if find(start) != find(end):
            union(start, end)
            answer += cost
            cnt += 1

        else:  # 이미 연결되어 있다면 넘어감
            continue

        # 다 연결시켰으면 중지
        if cnt == n - 1:
            break

    return answer