[백준] 가장 가까운 공통 조상 3584번 (c++)

출처 : 3584번: 가장 가까운 공통 조상 (acmicpc.net)

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

풀이 방법

처음에는 bfs 나 dfs를 활용하여 문제를 풀 생각을 하였지만 그러기엔 완전 탐색방법 밖에 생각이 안 났다. 

이 방법은 시간이 너무 오래 걸릴거 같아 다른 방법을 생각하였다.

처음에 입력 A, B를 받을 때 바로 배열 parent에 parent[B] = A로 저장하여 자신의 부모를 저장하였다.

그리고 공통 조상을 구할 노드 중 한 노드의 부모를 따라 올라가며 루트 노드가 나올 때까지 visited처리를 해준다

그 후 공통 조상을 구할 노드 중 위에서 처리 한 노드 말고 다른 하나의 부모를 따라 올라가며 visited가 나오면 ans에 그 visited가 나온 노드를 

ans 에 저장해 주어 답을 구한다.

 

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

int T, node1, node2, ans;
int visited[10001], parent[10001];

void solve() {

    int temp1 = node1;
    while (true) {
        if (temp1 == -1) {
            break;
        }
        visited[temp1] = 1;
        temp1 = parent[temp1];
    }
    int temp2 = node2;
    while (true) {
        if (visited[temp2] == 1)     {
            ans = temp2;
            break;
        }
        temp2 = parent[temp2];
    }
}

int main () {

    cin >> T;

    for (int i = 0;i < T;i++) {
        memset(visited, -1, sizeof(visited));
        memset(parent, -1, sizeof(visited));
        int N;
        cin >> N;
        for (int j = 0;j < N - 1;j++) {
            int A, B;
            cin >> A >> B;
            parent[B] = A;
        }
        cin >> node1 >> node2;
        solve();
        cout << ans << endl;
    }
    return 0;
}