[알고리즘 연습] 섬 연결하기 (프로그래머스 lv3, 파이썬)

문제

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

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

풀이

def solution(n, costs):
    ans = 0
    costs.sort(key = lambda x: x[2])
    routes = set([costs[0][0]])
    while len(routes)!=n:
        for i, cost in enumerate(costs):
            if cost[0] in routes and cost[1] in routes:
                continue
            if cost[0] in routes or cost[1] in routes:
                print(cost)
                routes.update([cost[0], cost[1]])
                # update : 값 여러개 추가
                ans += cost[2]
                costs[i] = [-1, -1, -1]
                break
    return ans

• kruskal 알고리즘의 축소판이라고 생각하면 쉽게 해결가능
• 가능한 간선(costs)를 cost 기준으로 오름차순 정렬 후 순서대로 확인
• 만약 다리가 연결하는 두 섬 모두가 현재 뭉치(routes)에 포함되어 있다면 사이클이 발생하므로 continue
• 그 외 둘 중 하나만 존재하는 경우를 찾아 뭉치(routes)에 포함시켜준다.
• 이를 모든 섬이 뭉치에 포함될때까지 반복