MST자바풀이

BOJ - 정복자 14950번 (JAVA)

❓ 문제 - 백준 정복자14950번 - JAVA 풀이법 출처 (https://www.acmicpc.net/problem/14950) 14950번: 정복자 서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재 www.acmicpc.net 📝 문제해결법 1. 이 문제는 MST(최소신장트리)로 풀이했다. 부모 찾기와 합집합을 구현하여 사이클이 생기지 않은 조건에서 최소신장트리를 만들어 모든 노드를 최소 비용으로 연결하도록 구현한다. 그러나 문제에서 최소신장트리를 구현하면서 최소 비용을 구할 때, 노드가 연결될 때마다 비용 t가 계속 추가적으로 증가한다는 것이다. 이것을 노드..