공부혜옹

백준 3584 가장 가까운 공통 조상 본문

공부합시다/Algorithm

백준 3584 가장 가까운 공통 조상

Blair06 2021. 10. 26. 15:07

처음엔 두가지 노드를 동시에 조상을 거슬러 오려니 어떻게 같은 조상을 찾을 수 있는지 조금 막막했다. 옛날에 비슷한 문제를 풀어봤던것같은데..ㅜㅜ 노드와 함께 깊이를 저장해 거슬러올라올까 하다가 굳이 그렇게 복잡하게 생각할 필요 없이 노드1을 루트 조상까지 먼저 쭉 방문하게 하고 나머지 노드2의 조상을 탐색하다가 노드1이 이미 방문한 노드를 공통조상으로 판별하였다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>

using namespace std;

int t, n;
int node1, node2;

void func (int tree[],int check[],int num){
    if(tree[num] == 0){
        if(check[num]==1){
            cout << num<<endl;
            return;
        }
        check[num]=1;
        return;
    }
    
    if(check[num] == 1){
        cout << num<<endl;
        return;
    }else{
        check[num] = 1;
        func(tree,check,tree[num]);
    }
    
   
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> t;
    
    while(t--){
        int tree[10001]={0,};
        int check[10001]={0,};
        cin >> n;
        for(int i=0; i<n-1;i++){
            int a, b;
            cin >> a >> b;
            //b의 부모는 a
            tree[b] = a;
            
        }
        //찾을 노드 2개
        cin >> node1 >> node2;
        
        func(tree,check,node1);
        func(tree,check,node2);
    }
    return 0;
}
반응형

'공부합시다 > Algorithm' 카테고리의 다른 글

백준 18119 단어암기  (0) 2021.10.31
백준 9372 상근이의 여행  (0) 2021.10.26
백준 1517 버블소트  (0) 2021.09.28
백준 5904 moo 게임  (0) 2021.09.28
백준 1485 정사각형  (0) 2021.09.14
Comments