[SWEA] 1251 하나로

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD

SW Expert Academy

풀이 과정

• 최소 신장 트리를 구현해야 겠다.
  • 프림 알고리즘
  • 크루스칼 알고리즘
  • Boruvka 알고리즘
• E = V^2인 그래프
  • 프림 알고리즘 -> 최소 비용을 완전 탐색을 사용하여 O(V) 찾기 -> O(V^2)
  • 크루스칼 알고리즘 -> 간선 정렬이 필요하기 때문에 O(V^2logV^2) = O(V^2logV)
  • Boruvka 알고리즘-> O(V^2logV)
• 프림 알고리즘으로 선택

풀이 코드

#include<iostream>
#include <queue>
#include <functional> 
#include <iomanip>

#define MAX 1001

using namespace std;

int x[MAX];
int y[MAX];
int visited[MAX];
long long distance_map[MAX];

long long dist_square(int a, int b){
    return 1LL * (x[a] - x[b]) * (x[a] - x[b]) + 1LL * (y[a] - y[b]) * (y[a] - y[b]);
}

int main(int argc, char** argv)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

	int test_case;
	int T;
    int N;
    double E;
    int node;
    long long answer;

    cin >> T;

	for(test_case = 1; test_case <= T; ++test_case)
	{
        
        cin >> N;

        fill(visited, visited + N, false);
        fill(distance_map, distance_map + N, (long long)1e18 + 7);
        answer = 0;
        for(int i = 0; i < N; ++i){
            cin >> x[i];
        }

        for(int i = 0; i < N; ++i){
            cin >> y[i];
        }

        cin >> E;

        priority_queue<pair<long long, int>, vector<pair <long long, int> >, greater< pair <long long, int> > > pq;
        
        distance_map[0] = 0;
        pq.push(make_pair(0, 0));

        while(!pq.empty()){
            int node = pq.top().second;
            pq.pop();
            if(visited[node]) continue;
            visited[node] = true;
            answer +=  distance_map[node];
            for(int nxt = 0; nxt < N; ++nxt){
                if(!visited[nxt] && distance_map[nxt] > dist_square(node, nxt)){
                    distance_map[nxt] = dist_square(node, nxt);
                    pq.push(make_pair(distance_map[nxt], nxt));
                }
            }
        }

        
        cout << "#" << test_case << " " <<  fixed << setprecision(0) << E * answer << '\n';
	}
	return 0;
}

• 자료형을 잘 설정하지 못해서 헤맸었습니다.
  • 세율 E(0<=E<=1)는 실수 인데 int형으로 선언
  • float형으로 바꾸었는데 20개 중 14개의 테스트 케이스 밖에 통과하지 못했음.
  • 정밀도 문제인 것 같아서 double 형으로 변경했더니 통과

개선 코드

#include <bits/stdc++.h>
using namespace std;
void solve() {
	int n;
	cin >> n;
	vector<int> x(n), y(n);
	for (auto &it: x) {
		cin >> it;
	}
	for (auto &it: y) {
		cin >> it;
	}
	double E;
	cin >> E;
	auto dist = [&](int i, int j) -> long long {
		return 1LL * (x[i] - x[j]) * (x[i] - x[j]) + 1LL * (y[i] - y[j]) * (y[i] - y[j]);
	};
	vector<long long> D(n, (long long)1e18 + 7);
	vector<bool> visit(n);
	int node = 0;
	visit[node] = true;
	long long ans = 0;
	for (int i = 0; i + 1 < n; ++i) {
		for (int nxt = 0; nxt < n; ++nxt) {
			D[nxt] = min(D[nxt], dist(node, nxt));
		}
		node = -1;
		for (int nxt = 0; nxt < n; ++nxt) {
			if (visit[nxt]) continue;
			if (node == -1 || D[node] > D[nxt]) {
				node = nxt;
			}
		}
		ans += D[node];
		visit[node] = true;
	}
	cout << fixed << setprecision(0) << E * ans << '\n';
}
signed main() {
	cin.tie(0)->sync_with_stdio(false);
	int T;
	cin >> T;
	for (int i = 1; i <= T; ++i) {
		cout << "#" << i << ' ';
		solve();
	}
	return 0;
}