최소 스패닝 트리 [백준 1197] - python

 

 

# 크루스칼 알고리즘
import sys
import heapq
input = sys.stdin.readline

def BOJ1197() :
  V, E = map(int, input().split())
  parent = [i for i in range(V+1)]
  l = []

  def find_parent(x) :
    if parent[x] == x :
      return x
    else :
      y = find_parent(parent[x])
      parent[x] = y
      return y

  def union_parent(a, b) :
    parent_a = find_parent(a)
    parent_b = find_parent(b)
    
    if parent_a > parent_b :
      parent[parent_b] = parent_a
    else :
      parent[parent_a] = parent_b

  for _ in range(E) :
    a, b, c = map(int, input().split())
    heapq.heappush(l, (c, a, b))
  
  result = 0
  
  while l :
    cost, a, b = heapq.heappop(l)

    if find_parent(a) != find_parent(b) :
      union_parent(a, b)
      result += cost
  
  print(result)

BOJ1197()

# 프림 알고리즘

import sys
import heapq
input = sys.stdin.readline

def BOJ1197() :
  V, E = map(int, input().split())
  
  graph = [[] for _ in range(V+1)]
  visited = [False for _ in range(V+1)]

  for _ in range(E) :
    a, b, c = map(int, input().split())
    graph[a].append([b, c])
    graph[b].append([a, c])

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

    while queue :
      curr_cost, curr_node = heapq.heappop(queue)
      if visited[curr_node] == False :
        visited[curr_node] = True
        result += curr_cost
        for next_node, next_cost in graph[curr_node] :
          heapq.heappush(queue, (next_cost, next_node))
          
    return result 

  print(prim())

BOJ1197()

 

 

접근 방법 :

1. 최소신장트리 문제 입니다.

최소신장트리는 신장트리중에 최소비용으로 만들수 있는 신장트리를 반환하는 개념입니다.

 

최소신장트리를 구하는 알고리즘에는 두개의 방법이 있습니다.

1. 크루스칼 알고리즘

2. 프림 알고리즘 

 

크루스칼 알고리즘은 이전의 글에서 다뤘던 적이 있으므로 

2022.03.20 - [알고리즘] - 네트워크 연결 [백준 1922] - python

이 글 에서는 프림 알고리즘에 대해서만 다루겠습니다

 

프림 알고리즘 

=> 그리디한 방법으로 최소 신장트리를 구하는 알고리즘

프림 알고리즘을 설명하기 위한 예시는 1922번 문제의 예시로 들겠습니다

 

동작순서

1. 선택된 노드들에 연결된 간선중 최소의 비용을 가진 간선을 선택합니다
2. 선택된 간선에 연결된 노드가 선택된 노드 리스트에 포함되어 있지 않다면 포함시킵니다(사이클 검사) -> 트리는 사이클을 이루지 않는 속성을 가지고 있음
3. 모든 노드를 방문할때 까지 1,2 번 과정을 반복합니다

 

 

초기상태

어느 노드로 시작해도 상관 없습니다.

저는 규칙적인것을 좋아하기 때문에 1번 노드부터 시작하겠습니다

 

먼저 1번에 연결된 간선중 가장 가치가 작은 1,3 간선을 선택합니다.

그 다음엔 1번, 3번 노드들에 연결된 간선들중 가장 작은 2의 가치를 가진 2,3 간선을 선택합니다.

1,2,3 노드에 연결된 간선들 중 가장 작은 가치는 5이지만 이미 1번 노드에는 방문을 했기 때문에 선택을 할 수가 없습니다.

차선책인 6으로 갑시다

이제 1,2,3,4가 선택된 노드 입니다. 

3의 가치를 가진 4,5 간선을 선택

8의 가치를 가진 5,6 간선 선택

 

알고리즘을 접하기 전에 굉장히 쫄아 있었지만 

한번 과정을 직접 그려보고 나니 이해하기 수웛하였습니다!!

화이팅!!

 

 

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

1197번: 최소 스패닝 트리