문제 설명
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를 그림으로 표현하면 다음과 같으며,
이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.
문제풀이
# n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때,
# 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때
# 필요한 최소 비용을 return하시오.
# costs의 길이 : i <= ((n-1) * n) / 2 -> 순서가 바뀌더라도 같은 연결로 봅니다
def solution(n, costs):
answer = 0
i = 0
j = 0
for i in range(costs):
if i <= ((n-1) * n) / 2:
for cost[i][j+2] in range(costs):
return answerKruskal 알고리즘을 사용하면 쉽게 풀린다.
Kruskal 알고리즘이란?
탐욕법을 이용하여 네트워크의 정점을 최소비용으로 연결하는 것이다.
여기서 탐욕법이란 그때그때 최선의 선택을 함으로써 최선의 결과에 도달하는 것이다.
Kruskal 알고리즘에서 핵심은 사이클이 생성되지 않게하는 것이다.
사이클이 생성되지 않기 위한 조건으로는 추가하려는 간선의 양끝점이 같은 집합에 속하지 않는 것이다.
이를 위한 판별법으론 Union-Find 알고리즘이 있다.
def solution(n, costs):
answer = 0
costs.sort(key = lambda x: x[2])
link = set([costs[0][0]])
# Kruskal 알고리즘으로 최소 비용 구하기
while len(link) != n:
for v in costs:
if v[0] in link and v[1] in link:
continue
if v[0] in link or v[1] in link:
link.update([v[0], v[1]])
answer += v[2]
break
return answer
문제 해설 작성
step 1
costs.sort(key = lambda x: x[2])
link = set([costs[0][0]])
costs.sort(key = lambda x: x[2])
before : [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]
after : [[0,1,1],[1,3,1],[0,2,2],[1,2,5],[2,3,8]]
<
lamda정렬 >
costs.sort(key = lambda x: x[2])
key를 사용해 2차원 배열 내부 특정 값을 기준으로 잡을 수 있다x[2]: 비용 기준으로 오름차순 정렬
❔ : 정렬을 하는 이유- 비용이 가장 낮은조건들을 먼저 연산
- 아래 set을 활용하기 위함
link = set([costs[0][0]])
시작 연결점을 set 리스트에 추가
step 2
while len(link) != n:
for v in costs:
if v[0] in link and v[1] in link:
continue
if v[0] in link or v[1] in link:
link.update([v[0], v[1]])
answer += v[2]
break
while len(link) != n:
- set 안에 연결된 모든 위치가 연결되기전까지 실행하는 조건
- 문제의 제한사항 중: 연결할 수 없는 섬은 주어지지 않습니다 를 만족
if v[0] in link and v[1] in link:
- 두 섬이 이미 더 낮은 가격으로 연결이 되었을 경우 무시
if v[0] in link or v[1] in link:
- 두 섬 중 하나가 연결이 되어있지 않을 때 비용을 더하기
link.update([v[0], v[1]])
- set.update( )는 중복을 제거
- 이미 섬이 연결되었을경우 중복된 섬은 추가되지 않고 최대 n 개의 섬을 유지
