크루스칼 (1) 썸네일형 리스트형 [Python] 프로그래머스 - 섬 연결하기 문제https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이최소 신장 트리 자료구조와 그래프 알고리즘과 관련된 문제이다. 신장 트리(Spanning Tree)란 주어진 그래프에서 최소한의 간선을 사용해 전체 노드를 포함하는 트리를 의미하며,다음과 같은 특징을 갖는다.V개의 노드와 E개의 엣지를 갖는 그래프 G가 주어질 때, 신장 트리는 V-1개의 엣지만을 사용한다사이클이 존재하지 않아야 한다.최소한의 간선을 사용해야 하므로, 사이클이 발생하면 신장 트리가 아니게 된다.주어진 전체 연결 그래프 G에.. 이전 1 다음