[PS/Python] 섬 연결하기 / Greedy / Kruskal / Union-Find / Prim
https://school.programmers.co.kr/learn/courses/30/lessons/42861 섬 연결하기 문제의 경우, n개의 섬이 있고, costs에 [섬1, 섬2, 비용] 형태로 연결 비용이 주어짐.모든 섬을 최소 비용으로 연결하는 방법을 찾아야 함.MST(최소 신장 트리, Minimum Spanning Tree) 알고리즘(Kruskal or Prim)으로 해결함최소 비용으로 연결해야 하므로 사이클이 생겨서는 안됨📌 사이클이 형성되면 안 되는 이유 (MST에서)➡ MST(최소 신장 트리, Minimum Spanning Tree)는 "모든 노드를 연결하면서도, 사이클이 없는 트리"여야 함.➡ 즉, 같은 노드를 두 번 방문하는 "순환 경로(사이클)"가 있으면 트리가 아님!1. MS..
Python/프로그래머스
2025. 3. 1. 15:00