[10주_5일차] 프로그래머스-섬 연결하기(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 find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

def union(parent, x, y):
    rootX = find(parent, x)
    rootY = find(parent, y)
    if rootX != rootY:
        parent[rootY] = rootX

def solution(n, costs):
    # 간선을 비용을 기준으로 정렬
    costs.sort(key=lambda x: x[2])
    
    parent = [i for i in range(n)]
    total_cost = 0
    
    for u, v, cost in costs:
        # 두 노드의 루트가 다르면 (즉, 연결되지 않았으면)
        if find(parent, u) != find(parent, v):
            union(parent, u, v)
            total_cost += cost
    
    return total_cost

 

 

<풀이과정>

 

• find 함수: 특정 노드 x가 속한 집합의 "루트"를 찾아 두 노드가 같은 집합에 속하는지를 확인
  • 트리 구조에서 노드 x가 속한 집합의 루트 노드 찾기
  • parent[x] != x인 경우, 즉 x가 자신의 루트가 아니라면, x의 부모를 재귀적으로 호출하여 최상위 루트 노드로 설정
• union 함수: 두 집합을 하나로 합치는 역할
  • find 함수를 사용하여 노드 x와 노드 y의 루트 노드 찾기
  • rootX와 rootY가 다르면, rootY를 rootX의 자식으로 설정하여 두 집합을 하나로 합치기
• costs 리스트:
  • [u, v, cost] 형태(u와 v는 연결할 두 섬의 번호이고, cost는 그 사이의 다리를 건설하는 비용)
  • 간선들을 비용(cost)을 기준으로 오름차순으로 정렬해 가장 작은 비용의 간선부터 선택할 수 있도록 함
• parent 리스트: 초기 상태에서 각 노드가 자기 자신을 부모로 갖도록 설정(처음에는 모든 섬이 독립된 집합)
• for문: 정렬된 간선들을 순서대로 처리
  • 각 간선에 대해, u와 v의 루트가 다르면 (즉, 두 섬이 아직 연결되지 않았다면) 이 간선을 선택\
  • union 함수를 호출 -> 두 섬을 하나의 집합으로 합치고, 해당 간선의 비용을 total_cost에 추가