섬 연결하기 - 프로그래머스 - 파이썬 풀이

문제 풀이

1. 섬의 좌표와 섬 간 거리가 주어졌을 때 최소한의 연결로 섬을 모두 잇는 문제입니다.
2. Kruskal 알고리즘을 쓰면 됩니다. get_minimum_spanning_tree
3. 먼저 edges(costs) 를 섬 간 길이 오름차순으로 sort 합니다.
4. 섬간 거리가 작은 edge부터 연결합니다. 이미 연결되어 있는 섬이면 건너뜁니다. (연결되어 있는 맨 끝의 섬 확인)
5. 연결된 섬들은 맨 끝 섬을 일치시킵니다. 연결시킨 edge에 대해서 mst에 저장합니다.
6. 모든 edge에 대해 4~5번을 반복합니다.
7. mst (연결시킨 모든 edge)를 이용해 total_costs 를 구합니다.

 

클린 코드 작성법

1. mst 와 같은 줄임말은 get_minimum_spanning_tree 와 같이 풀어 쓴 뒤 쓰면 좋습니다.

2. kruskal 알고리즘을 구현한 get_minimum_spanning_tree의 경우

   1. are_same_parent, find, union 3개의 함수로 나누어 구현했습니다.
   2. 복잡한 알고리즘일수록 나누어 구현하면 이해하기 편합니다.

3. are_same_parent 처럼 조건문의 가독성을 높일 수 있습니다.

 

해답 코드

def solution(n, costs):
    parents = initialize(n)
    mst = get_minimum_spanning_tree(parents, costs)
    answer = get_total_costs(mst)
    return answer

def initialize(n):
    vertices = list(range(0, n))
    parents = {}
    for vertice in vertices:
        parents[vertice] = vertice
    return parents

def get_minimum_spanning_tree(parents, edges):
    edges.sort(key=lambda x: x[2])
    mst = []
    for edge in edges:
        u, v, weight = edge
        if are_same_parent(parents, u, v):
            continue
        union(parents, u, v)
        mst.append(edge)
    return mst

def are_same_parent(parents, u, v):
    return find(parents, u) == find(parents, v)

def find(parents, v):
    while parents[v] != v:
        parents[v] = find(parents, parents[v])
        v = parents[v]
    return parents[v]

def union(parents, u, v):
    root1 = find(parents, u)
    root2 = find(parents, v)
    if root1 != root2:
        parents[root2] = root1

def get_total_costs(mst):
    total = 0
    for edge in mst:
        total += edge[2]
    return total

도움이 됐다면 공감버튼을 눌러주세요! 질문이 있다면 댓글 달아주세요!

 

문제 링크

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