목록2024/12/02 (1)

감자는 아직 꿈을 꾼다.

[프로그래머스-JAVA] Lv.3 섬 연결하기

알고리즘 : 최소비용신장트리 최소비용신장트리를 완성해가는 데 union find 알고리즘을 사용해서 사이클을 피하는 방식이다.Find에서 경로압축을 진행한다. 처음에 루트를 찾아가는 find함수에서 루트노드까지 재귀로 찾아가고나중에 return 되면 자식 노드들의 부모가 전부 루트노드로 갱신되며 추후의 탐색비용이 줄어드는 경로압축이 진행된다. find함수로 루트 노드를 찾아 다를 경우 union한다.이 과정에서 간선 사이 비용을 오름차순으로 정렬하여, 최솟값을 선택하면서 계속한다.최종적으로 간선의 수가 n-1 개일 경우 트리가 완성되었으므로 break한다. 문제설명https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스SW개발자를 위한..
코테적 감자/프로그래머스 2024. 12. 2. 21:59
이전 Prev 1 Next 다음