[탐욕법] 섬 연결하기

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

---

입출력 예

n	costs	return
4	[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]	4

---

입출력 예 설명

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

---

최소 신장 거리(MST, Minimum Spanning Tree) 문제입니다.

이 문제는 결국 모든 섬(노드)들이 하나로 이어져야 하기 때문에, 이들이 처음 시작하는 곳은 모두 같아야 한다는 걸 깨달아야 합니다.

위의 예시도 2번은 0번이랑 연결되어 있으니 0번 시작이란 걸 알 수 있죠. 여기서 0 = 1 = 2가 연결되어 있다면 1, 2의 시작은 0번이라는 걸 생각하면서 풀어야 합니다.

 

처음 시작하는 곳을 '부모'라고 말하겠습니다.

이 문제는 모든 노드의 부모가 같아질 때까지 반복하는 문제입니다.

 

개념을 설명하면 다음과 같습니다.

1. 부모를 기록할 리스트(배열)을 만든다.

부모를 전부 기록해줘야 합니다. 초기에는 아무 것도 연결되어 있지 않기 때문에 자기 자신이 부모입니다만, 나중에 연산을 하면서 부모가 바껴야 합니다.

 

2. 노드를 연결합니다.

노드와 노드를 연결합니다. 이 문제에서는 섬과 섬을 잇는 다리를 건설해 연결하는 것과 동일한 표현입니다.

A섬 - B섬을 이으며 다리가 건설됐다면, 자기보다 부모가 작은 경우에는 자신의 부모를 바꿔야 합니다.

위의 예시를 보자면, 0번과 1번이 이어지면서 1번의 부모는 0으로 바뀌는 과정을 말하는 겁니다.

부모가 작을 필요는 없지만 구현의 편의를 위한 거니까요.

 

3. 모든 노드의 부모가 같아질 때까지 반복한다.

부모가 같지 않다는 건 아직 연결이 되지 않았다는 뜻입니다.

모든 노드의 부모가 같아진다면 그건 노드들이 하나로 연결되었다는 걸 보장하죠.

 

이 규칙을 포함하는 게 크루스칼 알고리즘입니다. MST에서 최소 비용을 보장하는 알고리즘이죠.

파이썬으로 구현해보겠습니다.

def find_parent(parent, x):
    # 재귀로 구현한다.
    # 부모 노드를 반환한다.
    if parent[x] != x:
        return find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b):
    # 노드의 부모를 찾는다.
    ax = find_parent(parent, a)
    bx = find_parent(parent, b)
    
    # 작은 노드를 기준으로 부모를 합친다
    if ax < bx:
        parent[ax] = bx
    else:
        parent[bx] = ax

def solution(n, costs):
    # 가중치를 오름차순 정렬합니다.
    costs = sorted(costs, key=lambda x:x[2])
    # 부모 노드를 기록한다.
    parent = []
    for i in range(n):
        parent.append(i)
    # 총 비용
    total_cost = 0
    # 반복문 설정
    for i in range(len(costs)):
        a, b, cost = costs[i]
        # 부모가 다르다 = 노드가 연결되지 않았다
        if find_parent(parent, a) != find_parent(parent, b):
            # 부모를 합친다
            union_parent(parent, a, b)
            # 코스트를 더한다
            total_cost += cost
    return total_cost

 

코드의 흐름은 다음과 같습니다.

[사전작업]

1. costs를 비용 순으로 오름차순 정렬합니다. 최소 비용이기 때문에 가장 적은 쪽으로 이어야 합니다.

2. 부모를 자기 자신으로 설정합니다.

 

[통합작업]

1. costs만큼만 반복합니다.(costs는 같은 연결이 주어지지 않습니다.)

2. costs에서 연결할 a섬, b섬, 그리고 비용을 가져옵니다.

3. a와 b의 부모가 다르다면 = 연결이 되지 않은 상태라면

 - union_parent로 부모를 합쳐줍니다.

 - 그 후, 총 비용에 비용을 합산합니다.

 

find_parent는 섬의 부모를 찾는 함수입니다.

섬의 부모를 타고 타고 올라가면서 최종적인 부모를 반환하는 재귀함수입니다.

이 함수를 union_parent에 사용해서, 최종적인 부모들을 비교한 뒤 합쳐주는 겁니다.

 

크루스칼 알고리즘을 사용하는 MST 문제였습니다.