Notice
Recent Posts
Recent Comments
Link
반응형
공부혜옹
백준 3584 가장 가까운 공통 조상 본문
처음엔 두가지 노드를 동시에 조상을 거슬러 오려니 어떻게 같은 조상을 찾을 수 있는지 조금 막막했다. 옛날에 비슷한 문제를 풀어봤던것같은데..ㅜㅜ 노드와 함께 깊이를 저장해 거슬러올라올까 하다가 굳이 그렇게 복잡하게 생각할 필요 없이 노드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