[프로그래머스/c++] 섬 연결하기
크루스칼 알고리즘을 이용하는 문제이다. 처음에 문제를 보고 크루스칼 알고리즘이 떠오르지 않아 헤매다가 구글링을 통해 찾아보며 풀이 방법을 알게 되었다. 크루스칼 알고리즘이란? 간단하게 설명하면 그래프 내의 모든 정점들을 가장 적은 비용으로 연결하기 위해 사용된다. 그래프 내의 모든 정점을 포함하고 사이클이 없는 연결 선을 그렸을 때, 가중치의 합이 최소가 되는 상황을 구하고 싶을 때 크루스칼 알고리즘을 사용하게 된다. 즉 최소 신장 트리를 구하기 위한 알고리즘이다. 참고 https://chanhuiseok.github.io/posts/algo-33/ 알고리즘 - 크루스칼 알고리즘(Kruskal Algorithm), 최소 신장 트리(MST) ## chanhuiseok.github.io 다른 풀이 코드 #i..
알고리즘
2023. 1. 8. 22:52