알고리즘/백준
[MST] 백준 1717번 집합의 표현 - JAVA
2달 전에 맞췄던 문제, 또 풀어본다. 너무 오랜만에 알고리즘을 푸니... static 쓰는 것도 까먹는 나... 오늘은 오랜만에 MST 문제를 풀어보았다. 다시 개념을 살펴보자면 MST는 최소신장트리이다. 신장 트리 중에 사용된 간선들의 가중치 합이 최소인 트리이다. 도로망, 통신망, 유통망 등 비용을 최소로 해야 이익을 볼 수 있을 때 사용한다. 대표적인 방법으로 크루스칼과 프림이 있는데, 오늘의 문제는 합집합 연산을 하고, 같은 부모를 갖는지 확인해야하는 작업이었기 때문에 딱히 MST 문제는 아니지만, 크루스칼이 적격이라고 생각해서 크루스칼로 풀었다. 2달 전에 나도 크루스칼로 풀었다는 사실! ^^ 1. 출처 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\},..
