유령이 나오는 젤리하우스

Algorithm/SWEA

[SWEA 1251번] 하나로 (파이썬 풀이)

문제 바로 가기 🤔 문제 설명 및 입출력 - 문제의 저작권은 SWEA에 있습니다 - ✍ 접근 방법 이 문제는 시작 노드에서 도착 노드까지 도달하는 최소 비용을 구하는 문제가 아니라 ( 만약 문제가 이렇다면 다익스트라 계열 알고리즘으로 접근해야한다), 시작 노드에서 모든 노드를 순회하는데, 그 경로 중 최소 비용 경로를 구하는 문제이다. 모든 노드를 순회하는데, 최소 비용이 나오는 경로를 MST (Minimum Spanning Tree , 최소 신장 트리)라고 한다. MST를 구하는 대표적인 알고리즘으로는 프림 알고리즘과, 크루스칼 알고리즘이 있는데, 크루스칼 알고리즘은 union-find 개념을 적용해야하는데, 내가 이것에 익숙치 않아 프림 알고리즘으로 구현하기로 결심했다. 프림 알고리즘은 MST를 찾기..