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

방금 막 DFS/BFS 네트워크 포스팅을 했는데 알고리즘 하나 더 포스팅하려 합니다 ㅎㅎ (다른 주제로 포스팅하고 싶은데 노트북을 수리 맡긴 상황이라 알고리즘밖에 할 게 없네요 ㅜ)

바로 시작합니다.

이번에 풀어볼 문제는 역시 코딩 테스트 고득점 Kit에 들어있는 탐욕법 - 섬 연결하기입니다. 

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

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

문제 설명 & 제한사항

 

접근 방식:

1. 저는 가장 최소의 비용으로 섬을 연결해야 하기 때문에 가장 적은 비용이 드는 섬을 먼저 탐색하는 것이 좋을 것 같다고(?) 생각했습니다. 그래서 입력값인 costs를 가격, 첫번째 섬 번호, 두 번째 섬 번호순으로 오름차순 정렬했습니다. 

2. 섬이 연결되었는지 확인하는 딕셔너리를 하나 만듭니다. (아무리 비용이 작아도 다른섬과 연결이 되지 않는다면 결과에 추가하면 안 되기 때문입니다!)

3. costs의 첫 원소를 connected_islands라고 명명한 리스트에 추가 하고 추가된 섬의 is_connected = True로 설정합니다.

4. 연결된 섬의 개수가 n개가 될 때 까지 *반복문을 돕니다. 

*반복문 설명: cost는 [섬1, 섬2, 연결 비용]입니다. 그래서 만약 섬1 혹은 섬2가 다른 섬과 연결되어 있다면(is_connected = True 라면) 연결을 해도 좋은 상태라는 의미 입니다. 그래서 connected_islands에 연결되지 않았던 섬을 추가하고 새로 추가한 섬 역시 is_connected를 True로 설정합니다. 그리고 나서 answer에 비용을 더하고 for문 반목문을 빠져 나온 후 다시 반복문을 도는 형식입니다. 

-끝-

 

파이썬 코드

def solution(n, costs):
    answer = 0
    #1
    costs.sort(key = lambda x: (x[2], x[0], x[1]))
    
    #2
    is_connected = dict(zip(range(n), [False]*n))
    
    #3
    connected_islands = [costs[0][0],costs[0][1]]
    is_connected[costs[0][0]] = is_connected[costs[0][1]] = True
    
    answer += costs[0][2] # 처음에 하나의 연결을 추가하고 시작하기 때문에 answer에도 비용을 추가해줘야 합니다.
	
    #4
    while len(connected_islands) != n:
        for cost in costs:
            if is_connected[cost[0]] == True and is_connected[cost[1]] == False:
                connected_islands.append(cost[1])
                is_connected[cost[1]] = True
                answer += cost[2]
                break     
            elif is_connected[cost[0]] == False and is_connected[cost[1]] == True:
                connected_islands.append(cost[0])
                is_connected[cost[0]] = True
                answer += cost[2]
                break
    
    return answer