프로그래머스 Level3 "섬 연결하기"

문제

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

풀이

Kruskal 알고리즘을 이용하여 최소신장트리(MST)를 만들어야 한다.

Kruskal 알고리즘은 비용이 가장 낮은 간선부터 선택하는 그리디 알고리즘을 사용하되,
간선간의 사이클이 발생하지 않게 하는 것이 핵심이다.

이 문제에선 비용이 낮은 간선부터 반복하여
해당 간선의 두 개의 노드가 이미 check 세트리스트에 존재하면 사이클이 형성되게 되므로 해당 간선을 그대로 두고 반복을 진행한다.

간선의 두 노드중 하나의 노드가 check세트리스트에 존재하지 않을 경우 사이클이 형성되지 않으므로 해당 간선을 선택하고 costs에서 제외한다.

이 후 check의 노드 수가 n과 같아지면 반복을 종료하고 answer값을 리턴해준다.

Python 코드

def solution(n, costs):
  answer = 0
  # 비용을 기준으로 정렬
  costs.sort(key = lambda x: x[2])
  # set 자료형 선언
  check = set([costs[0][0]])

  while len(check) < n:
    # 비용이 적은 간선부터 추가
    # 사이클이 형성되는지 확인. 사이클이 형성되는 간선의 경우 넘어감
    for x in costs:
      if x[0] in check and x[1] in check:
        continue
      elif x[0] in check or x[1] in check:
        answer += x[2]
        check.update([x[0], x[1]])
        costs.pop(costs.index(x))
        break

  return answer