[프로그래머스] 섬 연결하기 - PYTHON

'프로그래머스 - 섬 연결하기'

Description

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

✔ My Solution - Kruskal

---

❔ - Kruskal 알고리즘이란? - 참고 : Heee's Development Blog

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]]

• 람다식 정력
• 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 개의 섬을 유지