PROGRAMMERS 42861: 섬 연결하기

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

---

Python

import heapq
 
 
def prim(start, graph):
    result = 0
    # 방문 확인을 위한 변수
    visited = [False for _ in range(len(graph))]
    task = []
    # 첫 시작점에서 갈 수 있는 범위를 등록
    for end, cost in enumerate(graph[start]):
        if cost != 0:
            heapq.heappush(task, (cost, (start, end)))
 
    # heap이 빌 때까지 반복
    while len(task):
        # 가장 작은 비용의 s -> e를 가져옴
        cost, (s, e) = heapq.heappop(task)
 
        # 둘중에 한곳이라도 방문이 안되어있으면
        if visited[s] == False or visited[e] == False:
            # 방문처리를 해주고
            visited[s] = visited[e] = True
            # 코스트를 증가
            result += cost
 
            # 다른 방문점을 추가시킨다.
            for end, cost in enumerate(graph[e]):
                if cost != 0:  # 코스트가 0이 아니면서
                    if not visited[end]:  # 방문한 지점이 아니면
                        heapq.heappush(task, (cost, (e, end)))  # 추가
    return result
 
 
def solution(n, costs):
    graph = [[0 for _ in range(n)] for _ in range(n)]
    for s, e, c in costs:
        graph[s][e] = c
        graph[e][s] = c
    return prim(0, graph)

FeedBack

1.  

---

 

 

 

cjw.git@gmail.com