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

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

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

#include #include #include #include #include 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<> t; while(t--){ int tree[10001]={0,}; int check[10001]={0,}; cin >> n; for(int i=0; i> a >> b; //b의 부모는 a tree[b] = a; } //찾을 노드 2개 cin >> node1 >> node2; func(tree,check,node1); func(tree,check,node2); } return 0; }

반응형

from http://hae-ong.tistory.com/84 by ccl(A) rewrite - 2021-10-26 16:27:15