크루스칼 알고리즘2 프로그래머스 - 섬연결하기 (파이썬) 프로그래머스 Lv3 - 섬연결하기 문제설명 n개의 섬 사이에 다리를 건설하는 비용이 주어지고, 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 구한다. 그래프에서 최소비용으로 모든 노드를 연결할 수 있는 최소신장트리를 찾는 문제이다. 문제풀이 1. 크루스칼 알고리즘 사용 # 부모 노드를 찾기 위한 함수 def find(parent,x): if parent[x]==x: return x else: return find(parent,parent[x]) # 부모 노드가 다를 경우 두 노드가 속한 집합을 합침 (두 집합에 간선을 연결한다고 생각하기) def union(parent,a,b): root_a=find(parent,a) root_b=find(parent,b) # 부모 노드는 무조건 작은 값을.. 2024. 3. 5. 크루스칼 알고리즘 (Kruskal Algorithm) 크루스칼 알고리즘을 이해하기 위한 필수 개념 1. 신장 트리 : 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 없는 부분 그래프를 의미한다. 2. 최소 신장 트리 : 신장 트리 중에서 최소한의 비용으로 구현된 신장트리를 의미한다. 크루스칼 알고리즘은 최소 신장 트리 알고리즘이며 그리디 알고리즘으로 구현된다 ! 크루스칼 알고리즘의 동작 과정 1. 간선 데이터를 비용에 따라 오름차순 정렬한다. 2. 모든 간선을 한번씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다. 사이클 발생하지 않는 경우 => 최소신장트리에 추가한다. 사이클 발생하는 경우 => 최소신장 트리에 추가시키지 않는다. 1. 간선 데이터를 비용에 따라 오름차순 정렬 간선 ( 3 , 5 ) ( 4 , 5 ) ( 1 , 3 ) (.. 2024. 3. 4. 이전 1 다음
