섬연결하기1 [프로그래머스] Lv3 - 섬 연결하기 접근 방식문제를 다른말로 해석하면, 문제가 모든 정점을 연결하는 간선들의 최소 비용 집합을 구하는 것입니다.이 문제는 최소 신장 트리(MST, Minimum Spanning Tree)를 찾는 문제라고 판단을 했습니다. 최소 신장 트리를 찾는 방법은 크게 크루스칼 알고리즘과 프림 알고리즘이 있습니다.프림 알고리즘이 크루스칼 알고리즘보다 비교적 더 쉽다고 판단이 되어 프림 알고리즘을 선택했습니다. 프림 알고리즘의 흐름은 어떻게 될까요?1. 시작 정점을 선택2. 우선순위 큐에서 가장 가중치가 작은 간선을 선택3. 해당 간선이 연결하는 정점이 MST에 포함되지 않았다면 추가4. 새로운 정점에서 갈 수 있는 간선들을 우선순위 큐에 삽입5. MST가 완성될 때까지 반복 예제를 분석하며 프림 알고리즘이 합당한지 보겠.. 2025. 2. 14. 이전 1 다음
