섬 연결하기

🔗 문제 링크

https://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의 비용이 주어지지 않습니다.

• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.

• 연결할 수 없는 섬은 주어지지 않습니다.

---

💡 풀이 (언어 : Python)

풀이에 실패했다. 크루스칼 알고리즘을 이용하는 최소 신장 트리 문제였다.
비용이 적은 순으로 정렬해서 활용하는 것까지는 좋았으나 하나의 집단인지 판별하는 것을 구현하기 어려웠다. 배웠던 내용을 복습하며 다시 풀어 보았다.

# 해당 노드의 부모 노드가 무엇인지 찾기
def find_parent(parent, x):
    
    # 해당 노드가 소속 집단의 부모 노드가 아니라면 부모노드 찾기
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    
    return parent[x]

# 같은 집단 = 노드들이 하나로 연결 됨
# 두 개의 노드를 연결해주는 함수
def union(parent, x, y):
    
    a = find_parent(parent, x)
    b = find_parent(parent, y)
    
    # 다른 노드와 연결시 숫자가 더 작은 노드를 부모 노드로 함
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
        
def solution(n, costs):
    answer = 0
    parent = []
    
    # 처음엔 자기 자신이 부모 노드라 해당 노드 값을 부모 노드값으로 
    for i in range(n):
        parent.append(i)
    
    # 비용이 적은 것 부터 추가하기 위해 비용 기준 오름차순 정렬
    # 이중 리스트라 안의 원소에 접근해서 변경
    # 비용의 순서가 맨뒤에 있어서 reverse 
    for cost in costs:
        cost.reverse() 
    # 이중 리스트 sort하면 원소 리스트의 앞 순서 인덱스 기준 정렬 = 비용 순
    costs.sort()
    
    for cost in costs:
        c, y, x = cost
        
        # 두 노드가 같은 집단이 아닌 경우만 연결
        # 부모 노드를 같게 해줘서 연결, 비용 계산
        if find_parent(parent, x) != find_parent(parent, y):
            union(parent, x, y)
            answer += c

    return answer