www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 문제에서 가중치는 주어지지 않는다. 따라서 우리가 직접 가중치값을 설정해줘야 하는데 각 별의 위치를 받으면 \(O(N^2)\)으로 가중치를 쉽게 설정해줄 수 있다. 거리 공식은 \(\sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}\) 이다. #include #include #include #include using namespace std; struct P { int u, v; double w; }; v..

www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 이산수학에서 최소 스패닝 트리를 구하는 방법에 대해 공부하길래 이왕 하는 겸 알고리즘으로 풀어보고 싶어서 구현해봤다. 처음에는 프림 알고리즘 먼저 구현해보려 했는데 유니온 파인드도 복습할 겸 해서 크루스칼로 풀었다. int find(int x) { return p[x] < 0 ? x : p[x] = find(p[x]); } bool merge(int x, int y) { x = find(x); y = find(y); if (x == y) return false; p[y] = x; return true..