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

문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42861

💻 문제 풀이 : Python

⭐ DFS 내 풀이 : TC 실패

globMinCost = [2134567890]
loadmap = []

def myMin(a, b):
    if (a >= b):
        return b
    else:
        return a

def allIslands(n, visited):
    for _ in range(n):
        if (visited[_] == False):
            return False
    return True

def Dfs(n, islands, isl, visited, cost, depth):
    if (globMinCost[0] < cost):
        return
    
    if (depth == n - 1):
        if allIslands(n, visited):
            print(loadmap, cost)
            globMinCost[0] = myMin(globMinCost[0], cost) 
        return
    
    for i in range(n):
        if (visited[i] == False) and (islands[isl][i] != 0) and i != isl:
            visited[i] = True
            cost += islands[isl][i]
            loadmap.append(i)
            Dfs(n, islands, i, visited, cost, depth+1)
            loadmap.pop()
            cost -= islands[isl][i]
            visited[i] = False

def solution(n, costs):
    answer = 0
    cost = 0
    depth = 0
    visited = [False for _ in range(n)]
    islands = [[0 for _ in range(n)] for _ in range(n)]
    
    # 섬 지도 만들기
    for i in range(len(costs)):
        a = costs[i][0]
        b = costs[i][1]
        islands[a][b] = costs[i][2]
        islands[b][a] = costs[i][2]
        
    print(islands)
    
    # 섬 전체 탐색하기
    for isl in range(n):
        if (visited[isl] == False):
            visited[isl] = True
            Dfs(n, islands, isl, visited, cost, depth)
            visited[isl] = False
            
    answer = globMinCost[0]
    
    return answer

⭐ 크루스칼(Kruskal)

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

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
        
def Sort(sub_li):
    sub_li.sort(key = lambda x : x[2])

def solution(n, costs):
    answer = 0
    parent = [0] * (n+1)
    
    for i in range(1, n+1):
        parent[i] = i
    
    Sort(costs)

    for e in costs:
        a, b, cost = e
        if find_parent(parent,a) != find_parent(parent, b):
            union_parent(parent, a, b)
            answer += cost
        
            
    return answer

---

📌 memo

Kruskal(크루스칼)

모든 정점들을 가장 적은 비용으로 연결하기 위해 사용하는 알고리즘
=> 모든 정점을 포함하고, 사이클이 없는 연결 선을 그렸을 때, 가중치의 합이 최소가 되는 상황
=> 최소 신장 트리를 구하기 위한 알고리즘

최소 신장 트리(MST : Minimum Spanning Tree)

최소 연결 = 간선의 수가 가장 적다
=> n 개의 node(정점)가 있을 때, n-1개의 edge(간선)을 갖는 경우

1. 그래프의 간선들을 가중치의 오름차순으로 정렬한다.
2. 순서대로 사이클을 형성하지 않는 간선을 선택한다. (부모 노드 비교)
3. 해당 간선을 현재 MST 집합에 추가한다.

ref)

출처 :
https://chanhuiseok.github.io/posts/algo-33/
https://life318.tistory.com/18