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

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

프로그래머스

내 풀이

1. 섬들을 모두 연결해야하고 이 때 최소 비용으로 연결하는 방법을 찾는다면 크루스칼 알고리즘을 사용할 수 있다

2. 섬들을 연결하는 비용으로 정렬한다

3. 적은 비용부터 하나씩 탐색하여 연결된 부모 노드를 찾거나 부모노드라면 더 작은 노드로 값을 바꾼다

def solution(n, costs):
    def getparent(parent,n):
        if parent[n]!=n:
            parent[n]=getparent(parent,parent[n])
        return parent[n]

    def union_parent(parent,a,b):
        a=getparent(parent,a)
        b=getparent(parent,b)
        if a>b:
            parent[a]=b
        else:
            parent[b]=a
            
    answer = 0
    costs.sort(key=lambda x:x[2])
    parent=[i for i in range(n)]
    
    for a,b,cost in costs:
        if getparent(parent,a)!=getparent(parent,b):
            union_parent(parent,a,b)
            answer+=cost
    return answer

 

다른 풀이

def solution(n, costs):
    costs = sorted(costs, key=lambda x:x[2])
    node = set([costs[0][0], costs[0][1]])
    answer = costs[0][2]

    while len(node) != n:
        for i in range(1, len(costs)):
            if costs[i][0] in node and costs[i][1] in node:
                continue
            if costs[i][0] in node or costs[i][1] in node:
                node.update([costs[i][0], costs[i][1]])
                answer += costs[i][2]
                break
    return answer

 

배운 점

1. 크루스칼 알고리즘에 대해 학습했다

2. 모든 곳을 연결하고 최저비용으로 한다면 크루스칼 알고리즘을 적용시킬 수 있다

 

크루스칼 알고리즘에 대해 학습을 원하는 분들은 아래 글을 참고하시면 됩니다

 

2023.05.22 - [IT] - [알고리즘] 크루스칼 알고리즘

[알고리즘] 크루스칼 알고리즘