[프로그래머스/Python] 섬 연결하기

문제 정보

제목 : 섬 연결하기

난이도 : Lv.3

사용 언어 : Python

문제 링크

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

프로그래머스

 

문제 설명

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

 

입출력 예 설명

costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

---

나의 풀이

섬 사이에 다리를 건설하는 비용이 적은 순으로 정렬하고, routes에 간선의 연결 정보를 담기위해 비용이 가장 적은 노드 하나를 저장합니다. routes의 길이가 n이 되기 전까지 반복하는 while루프를 이용합니다. 비용 리스트를 순회하는 for 루프를 이용해, 섬 2개가 전부 routes에 포함되어있다면 이를 이었을때 사이클이 형성되므로 continue합니다. 아니라면 l1이나 l2가 routes에 포함되어 있다면 routes에 섬을 추가하고, answer에 비용을 더한후 해당 for 루프를 종료합니다.

모든 반복이 끝나면 answer을 return합니다.

 

코드

def solution(n, costs):
    answer = 0
    costs.sort(key=lambda x:x[2])
    routes = set([costs[0][0]]) # 간선 연결 정보를 담는 set
    while len(routes) != n :
        for l1,l2,c in costs :
            if (l1 in routes and l2 in routes ): # 섬 2개가 둘다 연결되어 있는지 확인함
                continue
            if( l1 in routes or l2 in routes ): # 기존 경로 중 하나만 연결되어있다면 추가함
                routes.update([l1, l2])
                answer += c
                break
    return answer