[프로그래머스] 섬 연결하기 (python 파이썬)

문제

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

 

 

풀이 및 소스코드

cost[i][j][2] 즉, 비용을 기준으로 오름차순으로 정렬 후,

유니온 파인드 함수를 사용해서 같은 사이클에 있는 섬이 아니라면 연결해주는 방식으로 풀었다.

 

유니온 파인드란 각 점이 연결되어있는지 연결되지 않는지 부모를 확인해주고, 연결되있지 않다면 연결해주는 자료구조이다.

설명은 아래에 자세히 나와있다!

https://jainn.tistory.com/87

유니온 파인드(UNION-FIND) 파이썬 구현

def union(parent, x, y):
    x = find(parent, x)
    y = find(parent, y)
    if x==y:
        return
    parent[x] = y

def find(parent, x):
    if parent[x]==x:
        return x
    parent[x] = find(parent, parent[x])
    return parent[x]

def solution(n, costs):
    answer = 0
    cnt = 0
    parent = [i for i in range(n)]
    costs = sorted(costs, key=lambda x:x[2])
    for i in range(len(costs)):
        if find(parent, costs[i][0])!=find(parent, costs[i][1]):
            union(parent, costs[i][0], costs[i][1])
            answer += costs[i][2]
            cnt += 1
        if cnt == n:
            return answer
    return answer