프로그래머스_python_섬 연결하기

문제

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

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

풀이

신장트리

모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

최소신장트리

최소한의 비용으로 만들수 있는 신장트리

크루스칼 알고리즘

1. 간선을 비용이 적은 것부터 오름차순으로 정렬한다.

2. 각 간선이 사이클을 발생시키는지 확인한다.

2-1. 사이클을 발생시키지 않는다면 신장 트리에 포함한다.

2-2. 사이클을 발생시키지 않는다면 신장 트리에 포함하지 않는다.

풀이

전체적인 틀은 dfs & bfs 와 같다.

• graph에 연결된 노드와 가중치를 저장한다.
  • graph = {0: [(1, 1), (2, 2)], 1: [(1, 0), (5, 2), (1, 3)], 2: [(2, 0), (5, 1), (8, 3)], 3: [(1, 1), (8, 2)]}
• 모든 노드를 지날 때까지 탐색한다.
  • 처음 노드는 0
  • heapq를 사용하여, 비용이 가장 작은 노드를 꺼낸다.
  • 지나간 노드는 다시 방문하지 못하도록 해서 사이클의 발생을 막는다.

코드

import heapq
NOTPASSED = -1

def solution(N, costs):
    # save connection to graph
    graph = {i:list() for i in range(N)}
    for n, m, w in costs : 
        graph[n].append((w, m))
        graph[m].append((w, n))
    
    # search
    passed = [NOTPASSED for i in range(N)] # save weight
    heap = [(0, 0)]
    while heap : 
        w, n = heapq.heappop(heap)
        if passed[n]==NOTPASSED : # 지나간 적 없는 노드만을 탐색
            # save weight
            passed[n] = w
            
            # add next node
            for nw, cnode in graph[n] : 
                if passed[cnode]==NOTPASSED : # 지나간 적 없는 노드만을 탐색
                    heapq.heappush(heap, (nw, cnode))
    
    return sum(passed)

비슷한 문제

https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리