남극 기지 / ARCTIC 질문드립니다.

  • algospotJK
    algospotJK

    안녕하세요.

    오답으로 처리가 되어서요.

    혹시 빠진 부분이 있나 알려주실 수 있나요?

    현재 코드는 각 기지별 거리를 계산한 다음

    가장 가까운 거리부터 주파수의 범위로 설정하였을 때

    모든 기지를 방문할 수 있는지 검사하고 있습니다.

    감사합니다.

    #include <iostream>
    #include <vector>
    #include <math.h>
    #include <algorithm>
    #include <iomanip>
    
    using namespace std;
    
    vector<vector<int>> adj;
    vector<bool> visited;
    
    double distance(const pair<double, double> p1, const pair<double, double> p2) {
        return sqrt(pow(p1.first - p2.first, 2) + pow(p1.second - p2.second, 2));
    }
    
    int dfs(int here) {
        visited[here] = true;
        int ret = 1;
    
        for (int i = 0; i < adj[here].size(); ++i) {
            bool isConnected = adj[here][i];
            if (isConnected && !visited[i]) {
                ret += dfs(i);
            }
        }
        return ret;
    }
    
    double calcOutput(int N, const vector<pair<double, double>> points) {
        double ret = 0.0;
        vector<vector<double>> disArr = vector<vector<double>>(N, vector<double>(N, 0.0));
        vector<double> distV;
    
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (i == j)
                    continue;
                else {
                    disArr[i][j] = distance(points[i], points[j]);
                    if (i < j)
                        distV.push_back(disArr[i][j]);
                }
            }
        }
        sort(distV.begin(), distV.end());
    
        for (int i = 0; i < N; ++i) {
            if (distV.empty())
                break;
            double temp = distV[i];
            visited = vector<bool>(N, false);
    
            for (int i = 0; i < N; ++i) {
                for (int j = 0; j < N; ++j) {
                    if (i == j || disArr[i][j] <= temp) {
                        adj[i][j] = 1;
                    }
                    else
                        adj[i][j] = 0;
                }
            }
    
            if (dfs(0) == N) {
                ret = temp;
                break;
            }
        }
    
        return ret;
    }
    
    int main() {
        vector<double> answers;
        int C, N;
        double x, y;
    
        cin >> C;
        if (C < 1 || C > 50)
            exit(-1);
    
        for (int i = 0; i < C; ++i) {
            cin >> N;
            if (N < 1 || N > 100)
                exit(-1);
    
            vector<pair<double, double>> points;
            adj = vector<vector<int>>(N, vector<int>(N, 0));
            for (int j = 0; j < N; ++j) {
                cin >> x >> y;
                points.push_back(make_pair(x, y));
            }
            answers.push_back(calcOutput(N, points));
        }
    
        for (int i = 0; i < answers.size(); ++i) {
            cout << fixed << setprecision(2);
            cout << answers[i] << endl;
        }
    
        return 0;
    }
    

    4주 전
0개의 댓글이 있습니다.
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.