[Python] 백준 21924 도시 건설

문제 링크 : https://www.acmicpc.net/problem/21924

21924번: 도시 건설

 

1. 접근 방법

오랜만에 MSP 문제를 접근하여 방법이 잘 떠오르지 않아 여러 가지 방법을 시도하다가, 결국 union-find로 해결했다

 

2. 풀이 코드

🖥python 코드 링크: https://github.com/mintropy/baekjoon_py/blob/master/21000/21924.py

GitHub - mintropy/baekjoon_py: BOJ를 Python으로 해결한 코드의 저장소입니다.

📕코드 해설

각 도로를 비용 기준 오름차순으로 정렬 후, 하나씩 확인하면서 union-find 진행했다.

이후 한번 더 전체 점을 확인하며 모든 점이 하나로 합쳐졌는지, 그리고 각 점을 union 할 때, 더 번호가 작은 쪽으로 했기 때문에 최종적으로 1로 모두 연결되는지 확인하여 결과를 출력한다

 

3. 생각 정리

다양한 알고리즘을 길게 공부하지 못하고 시간이 흘러 돌아보니 잘 기억나지 않는 알고리즘과 방법도 많다.

그러나 일부 잘 단련된 알고리즘들은 또 그 나름대로 잘 풀려가는걸 보니, 짧지 않은 시간 동안 다양한 방면으로 잘 공부했나 싶은 생각도 든다.