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

문제

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

[나의 풀이]

⌛ 17분 소요

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 = find_parent(parent,start)
    end = find_parent(parent,end)

    if start<end:
        parent[end] = start
    else:
        parent[start] = end
    
def solution(n,costs):
    
    answer = 0
    
    islands = [i for i in range(n)]
    # print(islands)
    
    costs = sorted(costs, key=lambda x:x[2])
    print("costs : ",costs)
    
    for cost in costs:
        start,end,fee = cost
        print("islands : ",islands)
        print("start : ",start, " end : ",end)
        # start 와 end는 모두 연결이 가능
        # but, 부모가 다르면 크루스칼 연결이 안된 상태 => 어느 한쪽에 속하게 해야함
        if find_parent(islands,start) != find_parent(islands,end):
            print("if")
            union_parent(islands,start,end)
            answer += fee
        
    return answer

모든 노드를 연결할 수 있는 최소 비용 방법을 구현하는 크루스칼 알고리즘 문제입니다.

먼저 연결된 두 섬간의 이동 비용이 적은 순으로 정렬하였습니다. 그후 자기 자신 노드의 맨 끝단 노드를 찾는 find_parent 함수와 두 노드 집합을 연결하는 union_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

'나의 풀이'처럼 크루스칼 알고리즘을 활용하되 최소 비용으로 연결하는 과정에서 일정 조건을 걸고 break하여 더욱 빠른 풀이였습니다.

모든 N개의 섬을 연결하기 위해서 N-1개의 선만 있으면 되기때문에 선의 갯수를 파악하는 방법으로 구현하는 인상적인 풀이였습니다.

[다른 사람의 풀이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

set()을 활용하여 포함관계를 파악하는 크루스칼 알고리즘의 다른 표현 방식입니다.

최소 비용순으로 이동가능한 섬 리스트를 정렬한뒤 link 라는 set() 자료형에 시작점을 넣은 후 섬 이동가능한 섬 리스트를 돌며 시작점,도착점이 이미 link에 포함되어 있다면 이미 연결된 섬들 이므로 continue하고 아니라면 link에 포함하고 비용을 추가하는 방식입니다.

여기서 포인트는 '나의 풀이'에서는 find_parent, union_parent 함수로 섬을 연결하고 비용을 추가할지 여부를 판단했다면 위 풀이는 시작점,도착점이 이미 연결되어 있는지에 대해서는 포함관계로 파악하였다는 점입니다.

감사합니다.