전기가 부족해 [백준 10423] - python

 

import sys
input = sys.stdin.readline

def BOJ10423() :
  N, M, K = map(int, input().split())
  plants = list(map(int, input().split()))

  graph = []
  parent = [i for i in range(N+1)]

  for _ in range(M) : 
    graph.append(list(map(int, input().split())))
  
  graph.sort(key = lambda x : x[2])
  
  def find_parent(x) :
    if parent[x] == x :
      return x 
    
    y = find_parent(parent[x])
    parent[x] = y
    return y

  def union_parent(parent_a, parent_b) :
    if parent_a not in plants and parent_b in plants :
      parent[parent_a] = parent_b
    elif parent_a in plants and parent_b not in plants :
      parent[parent_b] = parent_a
    elif parent_a not in plants and parent_b not in plants :
      if parent_a > parent_b :
        parent[parent_b] = parent_a
      else :
        parent[parent_a] = parent_b

  result = 0 
  for a, b, cost in graph :
    parent_a = find_parent(a)
    parent_b = find_parent(b)

    if parent_a != parent_b and (parent_a not in plants or parent_b not in plants) :
      union_parent(parent_a, parent_b)
      result += cost

  print(result)
  
BOJ10423()

 

접근 방법 :

1. 크루스칼 알고리즘을 적용하였다. 

2. 처음엔 프림 알고리즘을 적용하고 가장 가중치가 높은 간선을 플랜트 -1 의 개수만큼 빼주는 방법으로 시도했었는데 실패하였다.

3. 크루스칼 알고리즘으로 교체하였고 부모의 검토조건에서 plants에 포함되어있는지의 여부를 통해 갱신 or 안갱신을 선택하게 하였다.

4. 크루스칼 알고리즘에 대한 정확한 이해가 필요할 것 같다.

 

 

 

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

10423번: 전기가 부족해