목록크루스칼 알고리즘 (2)

끵뀐꿩긘의 여러가지

Java - 크루스칼 알고리즘(Kruskal)

◎최소 스패닝 트리(minimum spanning tree) 스패닝 트리(spannig tree)란 신장 트리라고도 하며, 그래프 내의 모든 정점을 사이클 없이 포함하는 트리를 말한다. 하나의 그래프는 여러 개의 스패닝 트리를 가질 수 있으며, 사이클이 생기면 안 되므로 N개의 노드에 대하여 정확하게 N-1개의 엣지(간선)를 가진다. 최소 스패닝 트리(minimum spanning tree)란 MST라고도 하며, 그래프가 가질 수 있는 스패닝 트리중 간선의 가중치 합이 가장 작은 트리를 말한다. 스패닝 트리 또한 하나에 그래프에 여러 개일 수 있다. ◎크루스칼 알고리즘(Kruskal) 크루스칼 알고리즘은 간선을 중점으로 그리디하게 최소 스패닝 트리를 찾는 알고리즘이다. 1. 간선의 가중치 값을 기반으로 ..
JAVA/자료구조-알고리즘&함수 정리 2021. 5. 26. 15:38
프로그래머스 - 섬 연결하기 (sol.java)

◎문제 링크 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]] 4 programmers.co.kr ◎문제 파악 모든 섬을 연결하는 최소비용 구하기 - 최소비용을 구하는 문제이므로, 그리디 알고리즘을 이용하여 섬을 잇는 비용(간선 값)이 가장 작은 섬들부터 이어가야한다. --> 간선 값을 기준으로 정렬(heap 자료구조 사용, array로 넣어서 정렬하는것보다 빠르다) - 각 섬들이 어떤 섬과 이어졌는지 파악하기 위해서 배열(connect)을 만들어 이어진 섬 중에 가장 작은 번호의 섬을 집어 넣는다. 모든 배열의 값이 0이 되면(섬의 번호 중 ..
JAVA/문제풀이 - 프로그래머스 2021. 5. 24. 23:39
Prev 1 Next