코딩테스트 섬 연결하기 문제풀이

프로그래머스 섬 연결하기(level 3) 문제풀이

#부모 노드 찾기
def find_parent(parent, x):
  if parent[x] != x:
    parent[x] = find_parent(parent, parent[x])
  return parent[x]

#연결된 두 노드 합치기
def union_parent(parent, a, b):
  a= find_parent(parent, a)
  b= find_parent(parent, b)
  if a<b:
    parent[b] = a
  else: 
    parent[a] = b

def solution(n, costs):
  #n은 노드의 수
  length = 0
  parent = [0]*(n+1)
  for i in range(1, n+1):
    parent[i] = i
  costs.sort(key = lambda x:x[2])
  for c in costs:
    a, b, cost = c
    #같은 사이클이 아니면
    if find_parent(parent, a) != find_parent(parent, b):
      union_parent(parent, a, b)
      length += cost

  return length

그리디 ->크루스칼 알고리즘 문제

간선의 비용이 작은 것부터 반복하면서
두 노드의 부모노드가 같으면 사이클이 발생하므로 그것을 제외하고
비용들을 더해가면 된다

크루스칼 알고리즘에 대해 더 공부해보는 계기가 됨