[Python] BOJ(백준) 6497번 - 전력난

링크

https://www.acmicpc.net/problem/6497

난이도(solved.ac 참고)

골드4

풀이

오랜만에 쓰는 알고리즘 포스팅이다. 이번에는 최소 스패닝 트리의 대표적인 예시인 크루스칼 알고리즘을 사용하여 문제를 풀었다.

크루스칼 알고리즘의 구현 과정은 아래와 같다.

1) 간선 데이터를 비용에 따라 오름차순으로 정렬
2) 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인
  2-1) 사이클이 발생하지 않는 경우 최소 스패닝 트리에 포함
  2-2) 사이클이 발생하는 경우 최소 스패닝 트리에 포함 X
3) 모든 간선에 대해 2)의 과정을 반복

find_parent 함수를 통해 매개변수 x의 루트 노드를 찾고, union_parent 함수를 통해 두 원소가 속한 집합을 합친다.

parent 배열에서 우선 부모를 자기 자신으로 초기화한 뒤 간선 정보를 입력받고 그에 따라 edges에 (비용, a, b)순으로 넣는다.

그 다음 이 비용 순으로 오름차순으로 정렬한 뒤 a와 b의 부모가 같은 경우, 즉 사이클이 발생하지 않는 경우에 한해 그 두 가지를 합치고 비용을 더해주는 방식으로 진행했다.

 

이 문제에서 낚이기 쉬운 부분이었다고 생각되었던 부분은, 무한으로 반복하되 노드와 간선의 개수가 0 0인 경우에 break을 걸어서 종료시키도록 하는 것이었다. 입출력 예시 또한 여러개의 테스트 케이스를 가정하고 알려주는 방식으로 보이지 않을 수 있기 때문에 주의를 요한다. while True문에서 노드와 간선의 개수를 입력받은 뒤 둘다 0이면 break, 아니면 그 다음부터 기존 크루스칼 알고리즘을 진행하는 형태로 하였다.