[프로그래머스] 섬 연결하기 / Python / 테스트케이스(반례) 포함

문제주소 :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를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

 

<풀이법>

▒ 한줄 개념: Kruskal 알고리즘 ▒ 

탐욕법을 이용하여 MST(Min-Cost Spanning Tree)를 구하는 문제입니다.

대표적으로 사용할 수 있는 알고리즘으로는 Kruskal 알고리즘이 있습니다.

 

Kruskal 알고리즘의 핵심은 다음과 같습니다.

• 전체 간선 중에서 가장 비용이 작은 간선 선택
• 간선을 선택했을 때, 사이클이 만들어지면 안됨

주로 실패가 발생하는 부분은, 그룹핑에서 발생합니다.

사용된 반례들은 다음과 같습니다.

print(solution(4,[[0,1,1],[0,2,1],[1,2,1],[1,3,1],[2,3,8]]))
print(solution(5,[[1,2,3],[0,1,1],[0,4,5],[2,4,1],[2,3,1],[3,4,1]]))
print(solution(5,[[0,1,5],[1,2,3],[2,3,3],[3,1,2],[3,0,4],[2,4,6],[4,0,7]]))
print(solution(5,[[0, 1, 1], [2, 3, 1], [3, 4, 2], [1, 2, 2], [0, 4, 100]]))
print(solution(4, [[0, 1, 5], [1, 2, 3], [2, 3, 3], [3, 1, 2], [3, 0, 4]]))
print(solution(4,[[0,1,1],[0,2,2],[2,3,1]]))
print(solution(7, [[1,0,1],[3,2,1],[4,5,1],[3,5,9],[3,6,10],[1,6,1],[6,5,1]]))
print(solution(6,[[0, 1, 5], [0, 3, 2], [0, 4, 3], [1, 4, 1], [3, 4, 10], [1, 2, 2], [2, 5, 3], [4, 5, 4]]))
print(solution(6, [[0,1,1],[3,1,1],[2,3,3],[2,4,4],[5,4,5]]))
print(solution(5,[[0,1,1],[3,4,1],[1,2,2],[2,3,4]]))

 

<코드(Python)>

def solution(n, costs):
    answer = 0
    costs.sort(key = lambda x:x[2])
    edge_count = 0
    group = [-1 for i in range(n)]
    while edge_count < n-1:
        bridge = costs.pop(0)
        head, tail = (bridge[0], bridge[1]) if bridge[0] < bridge[1] else (bridge[1], bridge[0])
        if group[head] == group[tail] and group[head] != -1:
            pass
        else:
            if group[head] == -1 and group[tail] == -1:
                group[head], group[tail] = head, head
            elif group[tail] == -1:
                group[tail] = group[head]
            elif group[head] == -1:
                group[head] = group[tail]
            else:
                group_to_change = group[tail]
                for g in range(len(group)):   
                    if group[g] == group_to_change:
                        group[g] = group[head]
            edge_count += 1
            answer += bridge[2]

    return answer

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest