Level 3 섬 연결하기 Python3

https://programmers.co.kr/learn/courses/30/lessons/42861?language=python3 

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

 

최종 풀이

• GitHub -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_섬연결하기_kruskal.py

hwayeon351/Programmers-Algorithms

#Kruskal
def find(node, parent):
    if parent[node] == node:
        return node
    return find(parent[node], parent)
    
def make_set(node, parent, rank):
    parent[node] = node
    rank[node] = 0

def union(n1, n2, parent, rank):
    root1 = find(n1, parent)
    root2 = find(n2, parent)    
    if rank[root1] == rank[root2]:
        parent[root1] = root2
        rank[root2]+=1
    elif rank[root1] < rank[root2]:
        parent[root1] = root2
    else: parent[root2] = root1
    
def solution(n, costs):
    mst = []
    parent = dict()
    rank = dict()
    answer = 0
    for nd in range(n):
        make_set(nd, parent, rank)
    costs.sort(key = lambda x:x[2])
    for c in costs:
        n1, n2, cost = c
        if find(n1, parent) != find(n2, parent):
            union(n1, n2, parent, rank)
            answer += cost
            mst.append([n1, n2])
            if len(mst) == n-1: return answer
    return answer

 

• GitHub -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_섬연결하기_prim.py

hwayeon351/Programmers-Algorithms

#Prim
import math
def get_min_edge_island(islands, costs):
    min_cost = math.inf
    cost_idx = 0
    for i, cost in enumerate(costs):
        print(i, cost)
        #cycle check
        if cost[0] in islands and cost[1] in islands:
            continue
        #connection check
        if cost[0] in islands or cost[1] in islands:
            if cost[2] < min_cost: 
                min_cost = cost[2]
                cost_idx = i
    return cost_idx
            
def solution(n, costs):
    answer = 0
    graph = [[0]*n for i in range(n)]
    
    for c in costs:
        graph[c[0]][c[1]] = c[2]
        graph[c[1]][c[0]] = c[2]   
    print(graph)
    islands = {costs[0][0]}
    while len(islands) < n:
        cost_idx = get_min_edge_island(islands, costs)
        answer += costs[cost_idx][2]
        islands.update([costs[cost_idx][0], costs[cost_idx][1]])
    
    return answer

---

풀이 과정

풀이 시간 50분

그래프의 모든 정점이 간선에 의해 하나로 연결되면서 사이클을 형성하지 않는 '최소 비용 신장 트리(Mininum spanning tree)'의 기본 문제이다. MST는 크루스칼 알고리즘(Kruskal)과 프림 알고리즘(Prim)을 통해 구성할 수 있다.

따라서 위 두 가지 알고리즘을 각각 구현한 풀이 과정을 이야기 해 보겠다.

 

• 크루스칼 알고리즘 

가중치를 기준으로 간선을 정렬한 후에 MST가 될 때까지 간선을 하나씩 선택하거나 삭제해 나가는 방식이다.

가중치를 오름차순으로 정렬한 경우에는 간선을 하나씩 선택하면서 MST를 만들 수 있고, 가중치를 내림차순으로 정렬한 경우에는 간선을 하나씩 삭제하면서 MST를 만들 수 있다.

필자는 다리 건설 비용을 오름차순으로 정렬하여 다리를 하나씩 건설하면서 MST를 만드는 방법으로 문제를 풀었다.

간선을 추가할 때마다 사이클이 형성되는지 아닌지의 여부를 따져줘야 하는데 이를 위해 두 노드가 각각 속한 트리의 루트가 같은지의 여부를 판별할 수 있도록 find 함수를 구현하였다.

find 함수를 통해 연결하고자 하는 두 노드의 루트가 다른 경우 서로 다른 그래프라는 것을 증명할 수 있고, 이는 둘을 연결하더라도 사이클이 존재하지 않는다는 의미이다.

이렇게 find 함수를 통해 두 노드를 연결할 수 있다는 것을 알게 되어 연결을 진행할 때에는 Union-by-rank 기법으로 두 노드를 연결해주었다.

#그래프 생성시 parent와 rank 초기화
def make_set(node, parent, rank):
    parent[node] = node
    rank[node] = 0

#노드의 root 노드를 찾아주는 함수
def find(node, parent):
    if parent[node] == node:
        return node
    return find(parent[node], parent)

#Union-by-rank 기법
def union(n1, n2, parent, rank):
    #연결하고자 하는 두 노드의 root 구하기
    root1 = find(n1, parent)
    root2 = find(n2, parent)    
    #root1의 높이와 root2의 높이가 같은 경우, root1의 루트를 root2로 하여 두 트리를 합친다
    if rank[root1] == rank[root2]:
        parent[root1] = root2
        rank[root2]+=1
    #root1의 높이가 root2의 높이보다 작은 경우, root2의 자식으로 root1을 추가하여 두 트리를 합친다
    elif rank[root1] < rank[root2]:
        parent[root1] = root2
    #root1의 높이가 root2의 높이보다 큰 경우, root1의 자식으로 root2를 추가하여 두 트리를 합친다
    else: parent[root2] = root1
    
def solution(n, costs):
    mst = []
    #key = 노드, value = 노드의 부모 노드
    parent = dict()
    #key = 노드, value = 노드의 높이
    rank = dict()
    answer = 0
    
    #각 노드의 parent와 rank를 초기화하여 그래프를 초기화
    for nd in range(n):
        make_set(nd, parent, rank)
    #비용 순서대로 오름차순 정렬
    costs.sort(key = lambda x:x[2])

    for c in costs:
        n1, n2, cost = c
        #n1과 n2의 루트가 같은지 확인 -> 사이클이 형성되는지 체크
        if find(n1, parent) != find(n2, parent):
            #두 노드의 루트가 다르다면 연결
            union(n1, n2, parent, rank)
            #다리가 건설되었으므로 비용을 더하고 mst에 간선을 추가한다
            answer += cost
            mst.append([n1, n2])
            #간선이 정점 수보다 1 더 작은 경우 mst를 만족하므로 return
            if len(mst) == n-1: return answer
    return answer
#시간복잡도 = O(ElogE), #공간복잡도 = O(E)

시간복잡도는 costs를 정렬하는데에 O(ElogE)만큼 소요된다. MST를 구성하는데에서 Union-by-rank와 Path-comprehension 기법을 사용하면 시간복잡도는 O(1)이므로, len(costs)만큼 for문이 실행된다는 점에서 O(E)이 소요되지만 costs를 정렬하는 시간복잡도가 더 크기 때문이다.

공간복잡도는 costs가 Ex3 리스트이므로 S(3E) = O(E)이다.