글 읽기 - 2887번 어떤점이 문제인지 모르겠습니다.

tksgo2582 2년 전 0

안녕하세요.

이 문제를 크루스칼 알고리즘을 통해 구현해보았는데

7퍼센트에서 오답이 뜨네요..

어떤점이 문제인걸까요??

알려주시면 감사하겠습니다...

//행성터널
#include <bits/stdc++.h>
using namespace std;
#define MAX 100010

int N;
vector <pair<int,int>> x, y, z;
int parent[MAX]={0,};

int findf(int a){
    if(parent[a] == a)
        return a;
    return parent[a] = findf(parent[a]);
}
void unionf(int a, int b){
    a = findf(a);
    b = findf(b);
    if(a < b)           //
        parent[b] = a;
    else {
        parent[a] = b;
    }
}

int main(){
    cin >> N;
    int a, b, c;
    for(int i = 1 ; i <= N; i++){
        parent[i] = i;
        cin >> a >> b >> c;
        x.push_back({a,i});
        y.push_back({b,i});
        z.push_back({c,i});
    }
    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    sort(z.begin(), z.end());

    vector<pair<int,pair<int, int>>> edge;

    for(int i = 1; i < N; i++){
        edge.push_back({x[i].first - x[i-1].first, {x[i-1].second, x[i].second}});
        edge.push_back({y[i].first - y[i-1].first, {y[i-1].second, y[i].second}});
        edge.push_back({z[i].first - z[i-1].first, {z[i-1].second, z[i].second}});
    }
    sort(edge.begin(), edge.end());
    int result = 0;
    for(int i = 0 ; i < edge.size(); i++){
        int a, b, cost;
        cost = edge[i].first;
        a = edge[i].second.first;
        b = edge[i].second.second;

        if(parent[a] != parent[b]){
            unionf(a,b);
            result += cost;
        }
    }
    cout << result << "\n";
}

guswns137 2년 전 0

54 번 라인에서 실제 parent의 값의 변경은 find()에서 처리하기 때문에

부모요소가 같은 지를 비교하는 함수를 만들어

find()로 부모 요소를 찾아 같은지 확인 하면 될 것 같습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2887번 어떤점이 문제인지 모르겠습니다.

tksgo2582 2년 전 0

guswns137 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말