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

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

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

# 프로그래머스 섬 연결하기

def solution(n, costs):
    answer = 0
    costs.sort(key=lambda x: x[2])
    island = {}
    cnt = 0
    for i in range(n):
        island[i] = 0
    a, b, c = costs.pop(0)
    island[a] += 1
    island[b] += 1
    answer += c
    cnt += 1
    while cnt != n-1:
        for i in range(len(costs)):
            a, b, c = costs[i]
            if island[a] >= 1 and island[b] >= 1:
                continue
            elif island[a] >= 1 and island[b] < 1:
                island[a] += 1
                island[b] += 1
                answer += c
                cnt += 1
                costs.pop(i)
                break
            elif island[a] < 1 and island[b] >= 1:
                island[a] += 1
                island[b] += 1
                answer += c
                cnt += 1
                costs.pop(i)
                break
    return answer

둘 다 연결된 적이 없는 섬이라면 --> 방문x

연결된 적이 있는 섬 과 연결되지 않은 섬이라면 --> 방문 o

둘 다 연결된 적 있는 섬 ---> 방문x 

 

다음과 같은 방식으로 그리디하게 섬을 하나씩 확장해 나가면 된다.