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

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

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

풀이

비용을 오름차순으로 정렬하여 최소 비용이 먼저 오게함

costs의 첫번째 원소를 routes에 넣어서 첫 경로로 설정

모든 섬이 경로에 들어올때까지(`len(routes) == n`) 원소들을 반복하면서 경로를 탐색

만약 시작점과 도착점이 이미 경로에 있다면 넘어감

둘중 한점만 경로에 있다면 새로운 섬을 경로에 추가하고(set자료형이기 때문에 중복된 섬은 추가되지 않음) ans에 현재 섬의 비용을 추가한다. 또한, 현재 섬의 경로를 [-1, -1, -1]로 설정하여 다음 반복에 사용되지 않게 함

 

코드

def solution(n, costs):
    answer = 0
    costs.sort(key=lambda x:x[2])
    routes = {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:
                routes.update([cost[0], cost[1]])
                answer += cost[2]
                costs[i] = [-1, -1, -1]
                break
    return answer