글 읽기 - 어디가 틀렸는지 잘 모르겠어요.(c++)

112224 5년 전 1

맨 처음에 밀한 그래프의 풀이인줄 알고 prim으로 접근하여서 prim으로 풀려고 했는데

WA가 나왔어요ㅠㅠ 근데 같은 풀이를 kruskal로 바꾸니까 맞아서

수정 부분 위주로 틀린 부분을 찾는데 못찾겠어요 ㅠㅠ

고수님들의 도움 바랍니다.

//prim -> WA
#include<iostream>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef struct li
{
    ll d;
    int i;
}li;
bool operator <(li u,li v)
{
    return u.d>v.d;
}
typedef struct pl
{
    ll x,y,z;
    int num;
}pl;
int cnt;            //순서대로 x,y,z순 sort를 위함.
bool cmp(pl u,pl v)
{
    if(cnt==0)
    return u.x<v.x;
    else if(cnt==1)
    return u.y<v.y;
    else
    return u.z<v.z;
}
pl p[100001];
vector<li>graph[100001];        
bool visit[100001];


void init(int n)
{
    for(int i=0;i<n-1;i++)
    {
        ll x=p[i].x,y=p[i].y,z=p[i].z;
        int f=p[i].num;
        for(int j=i-1;j<=i+1;j+=2)
        {
            if(j<0) continue;
            ll x1=p[j].x,y1=p[j].y,z1=p[j].z;            //from - to 의 가중치 입력.(i와 i+1에
            int t=p[j].num;                                //대해 연결해주면 더 깔끔)
            ll co=min(abs(x-x1),min(abs(y-y1),abs(z-z1)));
            graph[f].push_back({co,t});
            if(j==n)graph[t].push_back({co,f});
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    
    int n;cin>>n;
    for(int i=0;i<n;i++)
        cin>>p[i].x>>p[i].y>>p[i].z,p[i].num=i;
    
    for(int i=0;i<=2;i++)
    {
        sort(p,p+n,cmp),cnt++;        //x,y,z순으로 정렬하고 graph 구성.
        init(n);
    }
    

    priority_queue<li> pq;
    pq.push({0,0});        //0번 노드에서 시작.
    cnt=0;    //방문한 지점의 개수
    ll ans=0;
    while(cnt!=n)        //cnt==n이면 모든 곳 방문이니 탈출
    {
        int now=pq.top().i;
        ll d=pq.top().d;pq.pop();
        if(visit[now])    //pq에 넣을 때 방문처리를 하면 최적해가 pq에 들어가지 않는 경우 발생.
        continue;
        ans+=d;            //방문하지 않은 정점의 경우 그 정점의 from-to 의 값을 ans에 더해줌.
        visit[now]=true;cnt++;
        for(auto k:graph[now])
        {
            if(!visit[k.i])
            pq.push(k);
        }
    }
    cout<<ans<<'\n';
}

//kruskal -> AC
#include<iostream>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef struct li
{
    ll d;
    int i,j;
}li;
bool operator <(li u,li v)
{
    return u.d<v.d;            //pq가 아니라 그냥 sort 여서 리턴결과 변경.
}
typedef struct pl
{
    ll x,y,z;
    int num;
}pl;
int cnt;
bool cmp(pl u,pl v)
{
    if(cnt==0)
    return u.x<v.x;
    else if(cnt==1)
    return u.y<v.y;
    else
    return u.z<v.z;
}
pl p[100001];
vector<li>graph;
int pare[100001];
int rk[100001];
int find(int u)
{
    if(u==pare[u])
    return u;
    return pare[u]=find(pare[u]);
}
void uni(int u,int v)
{
    int u1=find(u),v1=find(v);
    if(u1!=v1)
    {
        if(rk[u1]>rk[v1])swap(u1,v1);
        pare[u1]=v1;
        if(rk[u1]==rk[v1])rk[v1]++;
    }
}

void init(int n)
{
    for(int i=0;i<n-1;i++)
    {
        ll x=p[i].x,y=p[i].y,z=p[i].z;int f=p[i].num;
        int j=i+1;
        ll x1=p[j].x,y1=p[j].y,z1=p[j].z;int t=p[j].num;
        ll co=min(abs(x-x1),min(abs(y-y1),abs(z-z1)));
        graph.push_back({co,f,t});
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    
    int n;cin>>n;
    for(int i=0;i<n;i++)
        cin>>p[i].x>>p[i].y>>p[i].z,p[i].num=i,pare[i]=i;
    
    for(int i=0;i<=2;i++)
    {
        sort(p,p+n,cmp),cnt++;
        init(n);
    }
    ll ans=0;
    sort(graph.begin(),graph.end());
    for(li k:graph)
    {
        int u=k.i,v=k.j;
        if(find(u)!=find(v))
        {
            uni(u,v);ans+=k.d;
        }
    }
    cout<<ans<<'\n';
}

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

문제

문제

출처

ICPC

어디가 틀렸는지 잘 모르겠어요.(c++)

112224 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말