[Python | 프로그래머스 | Lv_3] 섬 연결하기

😉 아이디어

1. 크루스칼 및 유니온-파인드 알고리즘 활용

😉 풀이

def solution(n, costs):
    answer = 0
    sorted_cost = sorted(costs, key=lambda x: x[2])
    # Set 자료형 선언
    connect = {costs[0][0]}
    
    while len(connect) != n:
        #print(f'sorted_cost : {sorted_cost}')
        for cost in sorted_cost:
            # union-find 자료구조
            if cost[0] in connect and cost[1] in connect:
                continue
            if cost[0] in connect or cost[1] in connect:
                connect.update([cost[0], cost[1]])
                # print(f'커넥트 : {connect}')
                answer += cost[2]
                sorted_cost.remove(cost)
                break

    return answer

# 실패코드
# answer = float('inf')
# arr = []
# cost_arr = [[]]
# depth_end = -1

# def dfs(graph, start, depth, result, visited):
#     global cost_arr
#     global answer
#     global island_cnt
    
#     island_cnt = n - 1
#     if visited[start] == 1:
#         return
    
#     if depth == depth_end - 1:
#         # print(f'끝! 결과 : {result}')
#         answer = min(sum(result), answer)
#         return
    
#     for idx in range(len(graph[start])):            
#         temp_graph = graph.copy()
#         picked_value = temp_graph[start][idx]
        
#         #print(f'현재 탐색 : {temp_graph[start]} | 인덱스 : {idx} | 선택된 값 : {picked_value} )')        
#         temp_result = result.copy()
#         temp_result.append(cost_arr[start][picked_value])
        
#         temp_visited = visited.copy()
#         temp_visited[start] = 1
        
#         dfs(temp_graph, picked_value, depth + 1, temp_result, temp_visited)
    
# def solution(n, costs):
#     global answer
#     global arr
#     global cost_arr
    
#     arr = [[] for _ in range(len(costs) - 1)]
#     cost_arr = [[0] * (len(costs) - 1) for _ in range(len(costs) - 1)]
    
#     for cost in costs:
#         idx = cost[0]
#         path = cost[1]
        
#         arr[idx].append(path)
#         arr[path].append(idx)
        
#         cost_arr[idx][path] = cost[2]
#         cost_arr[path][idx] = cost[2]
    
#     for i in range(n):
#         visited = [0] * n
#         dfs(arr.copy(), i, 0, [], visited)
        
#     return answer

✔️ 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42861