프로그래머스: 섬 연결하기

문제

코딩테스트 연습 - 섬 연결하기

 

문제 풀이

 n개의 섬 사이에 다리를 건설하는 비용이 주어질 때, 모든 섬이 통행 가능한 최소 비용을 구하는 문제이다. 이 문제는 전형적인 `Kruskal 알고리즘` 문제이다. 해당 알고리즘 자체가 사이클을 이루지 않고, 최소 비용을 찾는 것이다. 이와 마찬가지로 문제에서도 "다리를 여러 개 건너더라도 해당 섬에 방문할 수 있으면 된다."라는 조건이 주어진다. 따라서 각 노드의 비용(건설하는 비용)을 기준으로 정렬한 후, 방문 여부에 따라 현재의 비용을 갱신하면 된다.

 

 주어진 예시를 Kruskal로 탐색하게 되면 위의 그림과 같은 순서로 탐색하게 된다. 따라서 최소 비용 4를 구할 수 있다.

 

코드

def solution(n, costs):
    answer = 0
    costs.sort(key=lambda x: x[2])
    visited = [True] + [False] * (n - 1)

    while not all(visited):
        for cur_node, next_node, cost in costs:
            print(visited)
            if visited[cur_node] and visited[next_node]:
                continue
            if visited[cur_node] or visited[next_node]:
                visited[cur_node] = visited[next_node] = True
                answer += cost
                break
    return answer