글 읽기 - 11438번 C++로 작성했고 '틀렸습니다'를 받았습니다.

elvpfhhrm 1년 전 0

고수님들의 조언을 부탁드립니다.

질문 게시판을 돌아다니며 더 좋은 풀이법을 보았지만 아무래도 제 코드의 문제점이 알고 싶어 질문을 남깁니다.

입력받은 간선 정보로 priority_queue를 사용해 sparseTable 테이블을 만들었습니다.

일단 예제와 질문게시판에 찾은 반례 2개는 정답이 나왔습니다만 제출하자 마자 '틀렸습니다'를 받았습니다.

어느 부분이 잘못돼서 오답이 나오는지 알려주실 수 있으신가요?

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
#define MAX 100000 + 1

vector<int> edges[MAX];
int Depth[MAX];
bool isVisited[MAX];
int parents[MAX];
int SpareTable[10+1][MAX];

int FindParent(int one,int two)
{
    if(Depth[one]>Depth[two])
    {
        int temp=one;
        one=two;
        two=temp;
    }
    //cout<<"now: "<<one<<" "<<two<<'\n';
    //cout<<"Depth: "<<Depth[one]<<" "<<Depth[two]<<'\n';
    
    int differ=Depth[two]-Depth[one];
    //cout<<"differ: "<<differ<<'\n';
    
    if(differ==0)
    {
        if(one==two){
            //cout<<"End"<<'\n'<<'\n';
            return one;
        }
        //cout<<"Next: "<<SpareTable[1][one]<<" "<<SpareTable[1][two]<<'\n';
        //cout<<"Depth: "<<Depth[one]<<" "<<Depth[two]<<'\n'<<'\n';
        return FindParent(SpareTable[1][one],SpareTable[1][two]);
    }
    else
    {
        if(differ>10)differ=10;
        
        //cout<<"Next: "<<one<<" "<<SpareTable[differ][two]<<'\n';
        //cout<<"Depth: "<<Depth[one]<<" "<<Depth[SpareTable[differ][two]]<<'\n'<<'\n';
        return FindParent(one,SpareTable[differ][two]);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N,M;
    cin>>N;
    for(int i=1;i<N;i++)
    {
        int first,second;
        cin>>first>>second;
        edges[first].push_back(second);
        edges[second].push_back(first);
    }
    
    Depth[1]=0;
    priority_queue<pair<int,int>> pq;
    pq.push({1,0});
    
    while(!pq.empty())
    {
        int now=pq.top().first;
        int depth=pq.top().second;
        pq.pop();
        
        isVisited[now]=true;
        
        for(int i=0;i<edges[now].size();i++)
        {
            int next=edges[now][i];
            if(isVisited[next])continue;
            pq.push({next,depth+1});
            Depth[next]=depth+1;
            //parents[next]=now;
            SpareTable[1][next]=now;
        }
    }
    for(int i=2;i<=10;i++)
    {
        for(int j=1;j<=N;j++)
        {
            if(Depth[SpareTable[i-1][j]]<1)SpareTable[i][j]=1;
            SpareTable[i][j]=SpareTable[i-1][SpareTable[i-1][j]];
        }
    }
    cin>>M;
    for(int i=0;i<M;i++)
    {
        int first,second;
        cin>>first>>second;
        
        cout<<FindParent(first,second)<<'\n';
    }
}

bnb2011 1년 전 3

오류가 나는 이유는,

1. Sparse Table의 크기가 충분하지 않습니다. 정점의 깊이는 최대 10만까지 될 수 있고, 현재 2^(n-1)번째 조상 노드를 SparseTable[1]에 저장하고 있으니 크기는 최소 [18][MAX]이 되어야 합니다.

2. 따라서 두 정점간 깊이의 차이도 최대 99999까지 될 수 있습니다. 41번째 줄을 지워야 합니다.

3. 두 정점의 깊이가 다를 때 깊이를 맞춰주는 과정이 잘못되었습니다. 현재 SparseTable[n][cur]에는 cur 정점의 2^(n-1)번째 조상이 저장되어있기 때문에, 2^k <= differ를 만족하는 가장 큰 k에 대해, FindParent(one, SparseTable[k+1][two])와 같은 형식으로 재귀호출이 이루어져야 합니다.

그리고 틀린 건 아니지만... 고치면 좋을만한 점들을 몇 개 짚어드립니다.

1. 정점을 순회할 때 Dijkstra를 사용할 이유가 없습니다. 모든 정점 사이의 거리가 같기 때문에 BFS로도 충분합니다.

2. 1번 노드의 부모를 1로 설정하면, 91번째 줄과 같은 예외처리를 할 필요가 없습니다.

3. 19~21번째 줄을 swap(one, two)로 대체할 수 있습니다.

elvpfhhrm 1년 전 0

감사합니다

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

문제

문제

출처

ICPC

11438번 C++로 작성했고 '틀렸습니다'를 받았습니다.

elvpfhhrm 1년 전 0

bnb2011 1년 전 3

elvpfhhrm 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말