프로그래머스 Lv3 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42861

[나의 풀이]

⌛ 19분

def find_parent(parent,x):
    
    if parent[x] != x:
        parent[x] = find_parent(parent,parent[x])
        
    return parent[x]

def union_parent(parent, start, end):
    start_p = find_parent(parent,start)
    end_p = find_parent(parent,end)
    
    if start_p<end_p:
        parent[end_p] = start_p
    else:
        parent[start_p] = end_p

def solution(n,costs):
    
    answer = 0
    parent = [i for i in range(n)]
    costs = sorted(costs, key=lambda x:x[2])
    
    for case in costs:
        start, end , cost = case
        
        if find_parent(parent,start) != find_parent(parent,end):
            union_parent(parent,start,end)
            answer += cost
            
    return answer

연결해야하는 섬의 갯수(n)가 주어지고 섬을 연결하는 케이스별 비용 리스트(costs)가 주어질 때, 모든 섬을 연결할 수 있는 최소한의 비용을 구하는 문제입니다.🐥🐥🐥

Union-Find 알고리즘을 활용한 최소 신장 트리(크루스칼) 알고리즘의 대표적인 활용 사례로 이를 구현하여 풀었습니다.

먼저 현재 자신 노드의 부모 노드를 찾아내는 find_parent()라는 함수를 구현하고 부모 노드가 서로 다른 노드들을 통합하는 union_parent()함수를 선언해줍니다.

모든 섬을 연결하는 최소 비용을 구하는 문제이므로 어떠한 다리들을 연결했을 때, 가장 적은 비용이 드는 섬들부터 연결을 시작하기 위해 costs를 비용이 적은 순으로 정렬하였습니다.

이후 섬 연결 케이스별 비용(costs)을 순차적으로 돌며 find_parent()로 부모가 다른 섬들을 연결시키며 비용을 추가하는 방식으로 구현됩니다. 만약 부모가 같다면 이는 이미 연결된 섬이므로 비용을 추가하지 않게 됩니다.

[다른 사람의 풀이1]

def ancestor(node, parents):
    
    if parents[node] == node:
        return node
    else:
        return ancestor(parents[node], parents)

def solution(n, costs):

    answer = 0
    edges = sorted([(x[2], x[0], x[1]) for x in costs])
    parents = [i for i in range(n)]
    bridges = 0

    for w, f, t in edges:
        
        if ancestor(f, parents) != ancestor(t, parents):
            answer += w
            parents[ancestor(f, parents)] = t
            bridges += 1
        if bridges == n - 1:
            break

    return answer

'나의 풀이'처럼 크루스칼 알고리즘을 활용한 풀이입니다. ancestor() 함수를 통해 현재 자신의 부모 노드를 찾는 방식입니다. 🐁🐁🐁

한 가지 다른 점은 섬 연결 케이스별 비용(edges)(섬1, 섬2, 비용) 값들이 주어질 때, 섬1의 번호가 섬2의 번호보다 반드시 작다는 것을 이용하여 번호 비교없이 바로 섬2를 기준으로 부모를 초기화했다는 점입니다.

[다른 사람의 풀이2]

def solution(n, costs):
    answer = 0
    costs.sort(key = lambda x: x[2]) 
    link = set([costs[0][0]])

    # Kruskal 알고리즘으로 최소 비용 구하기
    while len(link) != n:
        for v in costs:
            if v[0] in link and v[1] in link:
                continue
            if v[0] in link or v[1] in link:
                link.update([v[0], v[1]])
                answer += v[2]
                break
                
    return answer

연결된 섬별 최상위 부모 노드를 parent에 저장하는 형태가 아닌 set() 구조를 활용한 풀이입니다.🐕🐕🐕

적은 비용을 기준으로 정렬된 섬 연결 케이스별 비용(costs)을 돌며 현재까지 연결된 섬들(link)에 하나라도 연결되지 않은 섬(v[0] or v[1])이 있다면 두 섬(v[0], v[1])을 연결시키고 비용을 더하는 방식입니다.

find_parent(), union_parent() 함수를 따로 정의한 형태보다 while문, set()을 활용한 간결한 방식이었습니다.

감사합니다.