풀이 방법 모든 간선에 대해 크루스칼 알고리즘을 이용하면 간선의 개수가 N * (N - 1) / 2이기 때문에 메모리 초과가 발생한다. 그렇기 때문에 모든 간선에 대해 크루스칼 알고리즘을 적용하는 것이 아닌 x로 정렬하여 인접한 노드들 끼리의 간선, y로 정렬한 간선, z로 정렬한 간선들로만 크루스칼 알고리즘을 적용한다. 코드 #include #include #include #include using namespace std; using pii = pair; using piii = pair; struct T { int x, y, z, idx; }; priority_queue pq; int N, ans, cnt; T arr[100005]; int par[100005]; bool compare(T a, T ..

풀이 방법 크루스칼 알고리즘을 이용하여 풀이한다. 이미 연결 된 간선은 미리 연결해놓고 가장 거리가 짧은 간선을 뽑아 사이클이 있는지 확인하고 연결한다. 코드 우선순위큐를 이용한 구현 #include #include #include #include #include using namespace std; using ll = long long; using pll = pair; using pdll = pair; pll arr[1003]; ll N, M, par[1003], cnt, lev[1003]; priority_queue pq; ll dist(pll a, pll b) { return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (..

풀이 방법 최소 신장 트리(MST)를 구하는 문제이다. MST는 prim 알고리즘과 kruskal 알고리즘을 통해 구할 수 있다. 이 풀이는 prim 알고리즘을 이용했다. cf) prim 알고리즘을 모른다면 여기를 참고하세요 코드 #include #include #include using namespace std; using pdd = pair; using pdi = pair; pdd arr[102]; bool visited[102]; priority_queue pq; // 최소 힙 int N; double ans; //점과 점 사이의 거리 double dist(pdd a, pdd b) { return sqrt((a.first - b.first) * (a.first - b.first) + (a.secon..