[고득점 kit]_탐욕법_#5. 섬 연결하기

(문제 설명)

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

입출력 예

ncostsreturn

4

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

4

입출력 예 설명

costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

---

( 문제 해설 )

 

우선 설명을 듣기 전에 유니온 - 파인드 알고리즘을 알아야 합니다.

잘 설명해주신 분의 글을 첨부하겠습니다.

첨부할 글에서 유심히 보셔야 할 부분은

int find(int x)

void merge(int x, int y)

이 두 함수가 작동 절차가 어떻게 되는지 이해하고 제 설명과 코드를 보시면 이해가 빠를 듯합니다.

유니온 파인드(Union-Find) | begin_fill (ip99202.github.io)

유니온 파인드(Union-Find)

 

예시를 빌어서 설명을 하겠습니다. ( 그림 첨부 )

그림_알고리즘_진행_설명

유니온 파인드 알고리즘을 베이스로 다음과 같이 진행됩니다.

1. 비용 순으로 costs를 나열했으니 자동적으로 최소비용이 되게 섬이 연결됩니다.

2. 유니온 파인드를 이용하여 하나의 간선만 연결하게 됩니다

 

---

[ 코드 ]

 

# 5. 섬 연결하기 ( 유니 파인드 알고리즘 )
def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]


def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a > b:
        parent[a] = b
    else:  # a < b
        parent[b] = a


def solution(n, costs):
    # 자기 자신 초기화
    parent = [i for i in range(n)]
    # print(parent)
    sum_cost = 0
    # new
    costs.sort(key=lambda x:x[2])
    # print(costs)
    for i in costs:
        a, b, cost = i
        if find_parent(parent, a) != find_parent(parent, b):
            union_parent(parent, a, b)
            sum_cost += cost
    # print(parent)
    return sum_cost

---

후기

 

유니온 파인드 알고리즘 이전 오늘의 집 코테에서도

같은 알고리즘을 이용했었는데.

여기서는 거기보다 명확하게 이용하라고 알려준 문제입니다.