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

---

입출력 예

4

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

4

---

입출력 예 설명

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

---

🏝 풀이 코드

# 간선들이 이은 정점을 찾는 함수
def find(x, Vroot):
    if x != Vroot[x]:
        Vroot[x] = find(Vroot[x], Vroot)
    return Vroot[x]
    
def solution(n, costs):
    answer = 0

    # 연결 요소 중 가장 작은 값, 처음에는 자기 자신을 저장하는 Vroot
    Vroot = [i for i in range(n + 1)]

    # 간선을 가중치 기준으로 저장 및 정렬
    Elist = []
    for c in costs:
        # A번 정점 / B번 정점 / 가중치
        Elist.append(list(map(int, c)))
    Elist.sort(key=lambda x: x[2])

    answer = 0
    for s, e, w in Elist:
        # find 함수를 통해서 두 정점 찾기
        sRoot = find(s, Vroot)
        eRoot = find(e, Vroot)

        # 두 root가 다르다면 큰 root값을 작은 root값으로 만들어 연결되게 한다.
        if sRoot != eRoot:
            if sRoot > eRoot:
                Vroot[sRoot] = eRoot
            else:
                Vroot[eRoot] = sRoot
            # 가중치를 더한다.
            answer += w

    return answer

 

크루스칼 알고리즘으로 해결했다.

문제의 의도는 정확하게 MST(Minimum Spanning Tree, 최소 신장트리)를 구하는 문제이다. 최소 신장트리를 구할 수 있는 모든 알고리즘을 통해 풀이가 가능한 것으로 보인다.

 

문제에 대한 자세한 설명은 코드에 대한 주석이 담겨있으므로 이를 참고하길 바란다.

크루스칼 알고리즘의 기본형태이다.

 

만든 find 함수를 통해 s부터 이어진 트리, e부터 이어진 트리를 기반으로 두 개의 정점을 찾는다.

만약 s와 e가 모두 이어져서 sRoot == eRoot라면 이미 연결된 상태이므로 가중치 갱신이 필요 없다.

 

하지만 서로 다른 경우에는 두 노드 사이의 연결이 되지 않았다는 의미이므로 이어준다.

이어준다는 것은 Vroot에 저장하는데, 처음엔 인덱스 자기자신의 값을 가졌다가 연결되면 연결된 요소 중에서 가장 작은 값을 저장한다.

10개의 노드 중 1, 3, 6번 노드가 서로 연결되었고 나머지는 아니라면, Vroot는 [0, 1, 2, 1, 4, 5, 1, 7, 8, 9, 10]의 값을 가질 것이다.

그래서 if문 내부의 if문 연산은 연결된 것 중 가장 작은 것을 따라가게 설정하는 것이다.

 

가중치를 더하면서 다 이어질 때까지 하기만 하면 되는 이유는 가중치 기반으로 오름차순 정렬을 했기 때문에 최소 신장트리가 보장된다.