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

문제

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

프로그래머스

풀이

최소 신장 트리 자료구조와 그래프 알고리즘과 관련된 문제이다.

 

신장 트리(Spanning Tree)란 주어진 그래프에서 최소한의 간선을 사용해 전체 노드를 포함하는 트리를 의미하며,

다음과 같은 특징을 갖는다.

• V개의 노드와 E개의 엣지를 갖는 그래프 G가 주어질 때, 신장 트리는 V-1개의 엣지만을 사용한다
• 사이클이 존재하지 않아야 한다.
  • 최소한의 간선을 사용해야 하므로, 사이클이 발생하면 신장 트리가 아니게 된다.

주어진 전체 연결 그래프 G에서 위의 조건을 만족하는 신장트리는 하나 일수도, 여러개 일수도 있다.

 

최소 신장 트리(Miminum Spanning Tree)는 G에서 구성 가능한 신장 트리 중에서 가장 적은 비용으로 구성할 수 있는 신장 트리를 의미한다.

 

따라서, 위 문제를 풀기 위해서는 최소 신장 트리를 구하고 해당 트리를 구성하는데 필요한 비용을 return하면 해결할 수 있다.

각 노드 별로 BFS, DFS 알고리즘을 모두 적용하면 만들 수 있는 모든 신장 트리와 비용을 구할 수 있다,

하지만, 위의 방법은 그래프가 크고 복잡할 경우에 비효율적인 방식이다.

 

효율적으로 최소 신장 트리를 구하는 알고리즘에는 크루스칼 알고리즘, 프림 알고리즘이 존재한다.

 

크루스칼(Kruskal) 알고리즘

 

크루스칼 알고리즘은 Greedy 알고리즘을 기반으로 최소 신장 트리와 그 비용을 구하는 알고리즘이다.

비용을 기준으로 오름 차순 정렬된 전체 엣지를 순차적으로 탐색하면서, 신장 트리의 조건에 맞는 경우에만 선택함으로써 최소 신장 트리를 구할 수 있다.

 

1. 전체 엣지를 비용에 따라 오름 차순 정렬
2. 엣지 탐색
   • 신장 트리의 조건에 부합하는 경우(사이클이 존재하지 않아야 함)에 선택
     
     • root 노드 구하기(`find_parent`)
     • root 노드가 중복되지 않으면 트리에 추가(`union_parent')

# x의 부모 노드가, x일때 까지 재귀 호출 -> 처음 사용된 x의 부모노드 return됨
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) # a의 root node
    b = find_parent(parent, b) # b의 root node
    if a<b:
        parent[b] = a
    else:
        parent[a] = b
    
def solution(n, costs):
    answer = 0
    # 크루스칼 알고리즘
    parent = [0]*n
    # parent 초기화
    for i in range(n):
        parent[i]=i
    # cost작은 순서대로 오름차순 정렬
    costs = sorted(costs, key=lambda x:x[-1])
    # root노드 비교
    for a,b,c in costs:
    	# a,b노드가 서로 다른 root 노드를 가지는 경우, 트리에 추가
        if find_parent(parent,a)!=find_parent(parent,b):
            union_parent(parent,a,b)
            answer+=c
        # a,b 노드의 root 노드가 같은 경우에 추가하면, cycle 발생
    
    return answer

 

 

프림(Prim) 알고리즘

 

최초 시작 노드에서 출발해, 인접 노드 중에서 비용이 적은 노드를 선택해 트리를 확장시켜나가는 방식이다.

직관적으로 이해하면 BFS알고리즘과 Greedy 알고리즘을 결합한 방식이라고 볼 수 있을 것 같다.

 

# prim
def solution(n,costs):
    answer = 0
    import heapq
    # 연결 정보 초기화
    connect_dic = dict()
    for a,b,c in costs:
        tmp = {b:c}
        if a in connect_dic.keys():
            connect_dic[a].update(tmp)
        else:
            connect_dic[a] = tmp
        tmp = {a:c}
        if b in connect_dic.keys():
            connect_dic[b].update(tmp)
        else:
            connect_dic[b] = tmp
    # prim
    visited = [False]*n
    h = [(0,0)]
    while h:
        if all(visited):
            break
        c,v = heapq.heappop(h)
        # cost 순서대로 pop되기 때문에, heap안에 동일한 노드가 두번 이상 들어가 있을 수 있음
        # 그렇게 되면, cycle이 생기기 때문에 한번더 방문 여부 체크해야함
        if visited[v]: 
            continue
        visited[v] = True
        answer+=c
        for nv,nc in connect_dic[v].items():
            if not visited[nv]:
                heapq.heappush(h,(nc,nv))
                
    return answer