도시 분할 계획 [백준 1647] - python

import sys
import heapq
input = sys.stdin.readline

def BOJ1647() :
  N, M = map(int, input().split())
  graph = [[] for _ in range(N+1)]
  visited = [False for _ in range(N+1)]

  for _ in range(M) :
    A, B, C = map(int, input().split())
    graph[A].append([C, B])
    graph[B].append([C, A])

  
  def prim() :
    result = []
    queue = []
    queue.append((0, 1))

    while queue :
      curr_cost, curr_node = heapq.heappop(queue)

      if visited[curr_node] == False :
        visited[curr_node] = True
        result.append(curr_cost)
        if len(result) == N :
          break
        for next_cost, next_node in graph[curr_node] :
          heapq.heappush(queue, (next_cost, next_node))

    return sum(result) - max(result)

  print(prim())

BOJ1647()

 

접근 방법 :

1. 프림알고리즘으로 풀이를 하였다. 

 

2. 문제에서 마을을 두개로 분리해야 한다.
    최소 신장트리를 구한뒤에 그 중에 가장 큰 비용의 간선을 삭제하여 마을을 두개로 구분하여 주었다.

    위에서 언급한 대로 문제를 제출하였더니 시간 초과가 발생하였다.

 

3. 프림 알고리즘은 정점이 n개 일때 간선 n-1개를 선택하면 된다.
     if 문이 없으면 이미 간선을 다 선택했는데도 계속 탐색을 불필요하게 하고 있을수 있다.
     그래서 만약 선택한 간선이 N개 일때 while 문을 탈출 && 가치가 제일 비싼 간선을 삭제해주어 시간안에 통과 하였다.

 

 

 

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

1647번: 도시 분할 계획