[Programmers]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의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

코드

def solution(n, costs):
    answer = 0
    costs = sorted(costs, key = lambda cost : cost[2]) #비용을 기준으로 오름차순 정렬
    
    nodes = set([costs[0][0]]) #가장 적은 비용의 노드를 첫 번쨰 노드로 지정
    
    while len(nodes) != n:
        for index, cost in enumerate(costs):
            #현재 cost의 시작과 끝 노드가 모두 이미 nodes에 있다면 이미 연결되었으므로 pass
            if cost[0] in nodes and cost[1] in nodes:
                continue
            #현재 cost의 시작과 끝 노드 중 하나라도 nodes에 있다면 다음 연결될 수 있는 cost이므로 추가
            if cost[0] in nodes or cost[1] in nodes:
                answer += cost[2]
                nodes.add(cost[0])
                nodes.add(cost[1])
                costs.pop(index) #연결된 것은 지워주자
                break
    return answer

다른 사람의 풀이를 보니 크루스칼 알고리즘을 사용한 아주 멋진 풀이가 있어 추가로 작성하겠다.

#크루스칼 알고리즘을 사용한 풀이
def cruscal(node, parents):
    if parents[node] == node:
        return node
    else:
        return cruscal(parents[node], parents)
        
def solution(n, costs):
    answer = 0
    costs = sorted((cost, from, to) for from , to, cost in costs)) #cost를 맨 앞으로 보냄으로서 cost를 첫 번쨰 기준으로 정렬함
    parents = list(range(n))
    bridges = 0
    
    for cost, from, to in costs:
        if cruscal(from, parents) != cruscal(to, parents): #값이 다르다면 현재 연결되어야하는 노드들이 연결되지 않는 것임
            answer += cost
            parents[cruscal(from, parents)] = to #parents에 있는 값을 다음 연결된 노드 값으로 변경
            bridges += 1 #연결된 간선 추가
        if bridges == n - 1:
            break
    return answer

 

진행 과정

예제 #1

n = 4

costs = [[0, 1, 1],[0, 2, 2],[1, 2, 5],[1, 3, 1],[2, 3, 8]]

 

일반 풀이

1) costs = [[0, 1, 1], [1, 3, 1], [0, 2, 2], [1, 2, 5], [2, 3, 8]] #비용을 기준으로 오름차순 정렬

2) roots = {0} #가장 적은 비용의 첫 번쨰 노드 0을 시작으로 지정

3) answer = 1

 

4) roots = {0, 1}

5) costs = [[1, 3, 1], [0, 2, 2], [1, 2, 5], [2, 3, 8]]

6) answer = 2

 

7) roots = {0, 1, 3}

8) costs = [[0, 2, 2], [1, 2, 5], [2, 3, 8]]

9) answer = 4

 

10) roots = {0, 1, 2, 3}

11) costs = [[1, 2, 5], [2, 3, 8]]

12) return answer = 4

 

크루스칼 알고리즘 풀이

1) costs = [(1, 0, 1), (1, 1, 3), (2, 0, 2), (5, 1, 2), (8, 2, 3)] #비용을 첫 번째 기준으로 정렬

2) parents = [0, 1, 2, 3]

 

3) cruscal(from, parents) != cruscal(to, parents) = 0 != 1 = True

4) answer = 1

5) parents = [1, 1, 2, 3] #0이 이제 1에 연결되어 있으므로 1로 변경

 

6) cruscal(from, parents) != cruscal(to, parents) = 1 != 3 = True

7) answer = 2

8) parents = [1, 3, 2, 3] #1이 이제 3에 연결되어 있으므로 3으로 변경

 

9) cruscal(from, parents) != cruscal(to, parents) = 3 != 2 = True

10) answer = 4

11) parents = [1, 3, 2, 2]

12) return answer = 4