프로그래머스(탐욕법, Greedy)-섬 연결하기-Python

문제 설명

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.
다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

제한사항

• 섬의 개수 n은 1 이상 100 이하입니다.
• costs의 길이는 ((n-1) * n) / 2이하입니다.
• 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
• 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

입출력 예

n	costs	return
4	[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]	4

 

---

내 문제풀이

1. costs를 다리 건설 비용 기준 내림차순 정렬을 한다. 그리고 다리가 연결되어 이어진 섬을 1로 표시하는 리스트(island)를 모두 0으로 초기화를 한다.

2. 섬이 모두 연결된 경우인, island의 합이 섬의 갯수일 때까지 반복문을 수행한다.

3. costs의 한 원소에 있는 첫 번째 섬을 A, 두 번째 섬을 B라고 할 때, A와 B가 모두 island에 표시가 되어 있는 경우 무시하고 다음 원소를 확인한다. 

4. 하지만 A와 B 중 하나만 island에 표시가 되어 있는 경우 모두 모든 섬의 통행 가능한 최소 비용(answer)에 해당 원소의 비용을 더하고 island에 섬 A, B를 표시한다.

5. 여기에서 costs 길이만큼 반복하지 않고 while문을 도는 이유, 섬 A, B 모두 island에 없는 경우는 제외한 이유는 각각이 연결된 동 떨어진 섬들이 생기는 것을 방지하기 위해서이다. 이렇게 하지 않는다면, 섬 1-2, 섬3-4-5 와 같이 각각 따로 연결되어 있는 상태에서 해당 함수가 끝나버리게 된다.

내 코드 - 파이썬

def solution(n, costs):
    answer = 0
    island=[0]*n 
    costs.sort(key=lambda x:x[2])
    island[costs[0][0]]=1
    new_island=[]
    
    while(1):
        if sum(island)==n:
            break
        for cost in costs:
            if island[cost[0]] and island[cost[1]]:
                continue            
            elif island[cost[0]] or island[cost[1]]:
                answer+=cost[2]
                island[cost[0]]=1
                island[cost[1]]=1
                break
            
    return answer