[SWEA] 1248. [S/W 문제해결 응용] 3일차 - 공통조상 (C++)

문제 URL : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15PTkqAPYCFAYD&categoryId=AV15PTkqAPYCFAYD&categoryType=CODE&problemTitle=%EC%9D%91%EC%9A%A9&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=2

SW Expert Academy

문제 접근법 : 

LCA를 사용해서 풀었는데 LCA를 굳이 사용하지않더라도 ,,BFS 든 DFS 여러번 써도 풀리는 문제라

문제의 기본기를 묻는 문제더군요

 

소스코드 : 

#include<bits/stdc++.h>
using namespace std;

int n,e,a,b;
vector<vector<int>> v,parent;
vector<int> cnt,depth;

void input(){
    cin>>n>>e>>a>>b;
    depth=cnt =vector<int>(n+1,1);
    v=vector<vector<int>>(n+1);
    int x,y;
    for(int i=0;i<e;i++){
        cin>>x>>y;
        v[x].push_back(y);
    }
}

int lca(int x,int y){
    if(depth[x]>depth[y])swap(x,y);
    for(int i=19;i>=0;i--){
        if(depth[y]-depth[x] >=(1<<i))y=parent[i][y];
    }
    if(x==y)return x;

    for(int i=19;i>=0;i--){
        if(parent[i][x]!=parent[i][y]){
            x=parent[i][x];
            y=parent[i][y];
        }

    }
    return parent[0][x];
}
void dfs(int cur,int before=0,int h=0){
    parent[0][cur]=before;
    depth[cur]=h;
    for(int next:v[cur]){
        dfs(next,cur,h+1);
        cnt[cur]+=cnt[next];
    }
}

void solve(){
    parent =vector<vector<int>>(20,vector<int>(n+1));
    dfs(1);
    for(int i=1;i<20;i++){
        for(int j =1;j<=n;j++){
            parent[i][j]=parent[i-1][parent[i-1][j]];
        }
    }
    int node = lca(a,b);
    cout<<node<<" "<<cnt[node]<<"\n";

}
int main(){
    
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.txt","r",stdin);
    int test;
    cin>>test;
    for(int i=1;i<=test;i++){
        cout<<"#"<<i<<" ";
        input();
        solve(); 
    }
}

 

궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.