기록

문제https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4programmers.co.kr풀이신장트리모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프최소신장트리최소한의 비용으로 만들수 있는 신장트리크루스칼 알고리즘1. 간선을 비용이 적은 것부터 오름차순으로 정렬한다.2. 각 간선이 사이클을 발생시키는지 확인한다.2-1. 사이클을 발생시키지 않는다면 신장 트리에 포함한다.2-2. 사이클을 발생시키지 않는다면 신장 트리에 포함하지 않는다.풀이전체적인 틀은 dfs & bfs 와 같다.graph에 연결된 노드와 가중치를 저장한다.graph = {0..