[프로그래머스][level3] 섬 연결하기 - python(크루스칼 알고리즘)

문제 링크

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

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

풀이 

• 크루스칼 알고리즘 사용 
  • 그리디 알고리즘을 사용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적의 해답을 구하는 것
  • MST(최소 신장 트리) 조건

    1. 최소 비용 간선으로 구성

    2. 사이클을 포함하지 않음 
  • 알고리즘의 동작 방법
    1. 그래프들의 간선들을 가중치의 오름차순으로 정렬
    2.  정렬된 간선 리스트에서 순차적으로(가장 낮은 가중치부터) 사이클을 형성하지 않는 간선 선택 : 'union-find 알고리즘' 이용하여 사이클 생성 여부 확인
    3. 해당 간선을 MST의 집합에 추가 

 

• 1. # 크루스칼 알고리즘(그리디 알고리즘)
     def solution(n, costs):
       # cost 기준으로 오름차순 정렬 
       costs.sort(key = lambda x : x[2])
       # 첫번째 섬 연결 정보 connect에 추가. 중복 제거를 위해 set으로 설정 
       connect = set([costs[0][0],costs[0][1]])
       # 첫 가중치 
       answer = costs[0][2]
       
       while len(connect) < n:
         for cost in costs:
           # 다음 섬의 출발지와 목적지가 모두 connect에 존재하면 넘어감 
           if cost[0] in connect and cost[1] in connect:
             continue
           # 두 섬 중 하나만 connect에 있는 경우 추가한 후 answer에 가중치 더함 
           if cost[0] in connect or cost[1] in connect:
             connect.update([cost[0],cost[1]])
             answer += cost[2]
             break 
     
       return answer

+ 2022.05.17 다시 풀이

- union, find 알고리즘을 사용한 크루스칼 알고리즘으로 풀이 

# 부모 찾는 함수 
def find(parent, x):
    if x != parent[x]:
        parent[x] = find(parent,parent[x])
        
    return parent[x]
 
# 두 집합 합치는 함수 
def union(parent, x,y):
    x = find(parent, x)
    y = find(parent, y)
    
    if x == y:
        return 
    
    if x < y :
        parent[y] = x
    else:
        parent[x] = y

def solution(n, costs):
    answer = 0
    parent = [0] * n
    
    for i in range(n):
        parent[i] = i
            
    edges = []
    
    for a, b, c in costs:
        edges.append((c,a,b))
        edges.append((c,b,a))
        
    edges.sort()
    
    for edge in edges:
        cost, a, b = edge
        # 같은 집합에 속하지 않으면 
        if find(parent,a) != find(parent,b):
            answer += cost
            union(parent,a,b)
            
    return answer