[프로그래머스]섬 연결하기 - 그리디, 최소 신장 트리, Prim

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

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

 

# 프림 알고리즘, 우선순위큐 이용(heapq)
import heapq

def solution(n, costs):
    answer = 0
    
    # 각 정점의 인접정보와 가중치를 저장하는 리스트
    cost_all = [[]for _ in range(n)]
    
    # 방문 체크를 위한 리스트
    visited = []

    # 우선순위큐 사용
    heap = []
    # 시작정점을 0으로 선택, 가중치도 0으로 설정(cost, start)
    heapq.heappush(heap, [0, 0]) 
    
    # 정점의 인접정보, 가중치 갱신
    for cost in costs:
        s, e, w = cost
        cost_all[s].append([w, e])
        cost_all[e].append([w, s])
        
    cnt = 0
    # 연결된 정점의 개수가 n-1이 되면 반복을 종료함
    while cnt < n:
        # 가중치가 가장 작은값을 계속 꺼내서 사용함
        w, s = heapq.heappop(heap)
        if s in visited:
            continue
        # 방문을 하지 않은 경우에만 진행
        visited.append(s)
        answer += w
        cnt += 1
        for cost in cost_all[s]:
            # 방금 방문한 정점과 연결되어있는 정점의 가중치 정보를 큐에 넣음
            heapq.heappush(heap, cost)

    return answer

 

문제 해결 Point

지난번의 크루스칼 알고리즘 풀이에 이어, 프림 알고리즘으로 푸는 방법을 소개한다.

 

Kruskal vs Prim

크루스칼 알고리즘과 프림 알고리즘의 대표적인 차이점은 아래와 같다.

• 크루스칼은 임의의 정점에서 시작하여 가중치가 낮은 간선부터 사이클이 생기지 않도록 선택해나가는 것이고,
  프림은 하나의 정점을 정하고 인접 정점중 가중치가 낮은 간선을 계속 골라가는 알고리즘이다.

 

그럼 위의 코드를 순서대로 풀어 설명해보겠다.

1. 시작정점을 0, 가중치를 0으로 설정하여 우선순위큐인 heap 리스트에 값을 지정해준다.
2. 각 정점의 인접 정보와 가중치를 저장하기 위해 cost_all 이라는 리스트를 만들어 값을 넣어준다.
   

   [[0번 정점의 인접 정보, [가중치, 연결된 정점] [1, 1], [2, 2]], [1번[1, 0], [5, 2], [1, 3]], 
    [2번[2, 0], [5, 1], [8, 3]], [3번[1, 1], [8, 2]]]

3. 연결된 정점의 개수가 n-1개가 될 때 까지 반복을 진행한다.
   1. 우선순위큐인 heap에서 가중치가 가장 낮은 것을 꺼낸다. (pop)
   2. 만약 해당 정점을 방문하지 않았더라면 방문처리, 가중치 더하기를 진행한다.
   3. 방금 방문한 정점의 정보를 우선순위큐에 넣어줌으로써 가중치 정보들을 갱신하여 준다.

 

동일한 문제이지만 서로 다른 알고리즘으로 문제를 풀 수 있기에 두 알고리즘으로 모두 풀이해보았습니다.