백준 3584 - 가장 가까운 공통 조상(C++)

문제 링크입니다. https://www.acmicpc.net/problem/3584

3584번: 가장 가까운 공통 조상

공통 조상을 찾는 문제입니다.

 

두 노드가 주어지고 서로의 가까운 공통 조상을 찾는 문제입니다.

 

이 문제를 푸는 방법은 두 노드 중 하나의 노드를 선택해 해당 노드의 부모를 찾아준 뒤, 찾은 부모들의 값을 1로 바꿔줍니다.

남은 노드 하나를 탐색해, 해당 노드의 부모를 찾아줍니다.

이때, 노드의 값이 1인 것이 있다면, 해당 노드가 공통 조상이라는 의미입니다.

 

자세한 것은 코드를 참고해주세요

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#define P pair<int, int>
#define F first
#define S second
using namespace std;

int test_case;
int N;
int check[10001], parent[10001];
int node1, node2;

void solve(){
   check[node1] = 1;
   while(node1 != parent[node1]){
       node1 = parent[node1];
       check[node1] = 1;
   }
   while(1){
       if(check[node2]){
           cout << node2 << "\n";
           break;
       }
       node2 = parent[node2];
   }
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> test_case;
    for(int k = 0; k < test_case; k++){
        cin >> N;
        memset(check, 0, sizeof(check));
        for(int i = 1; i <= N; i++) parent[i] = i;
        for(int i = 1; i < N; i++){
            int x, y;
            cin >> x >> y;
            parent[y] = x;
        }
        cin >> node1 >> node2;
        solve();
    }
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요