[백준] 11437 LCA

문제
N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.

두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.

입력
첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.

출력
M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.

예제 입력 1
15
1 2
1 3
2 4
3 7
6 2
3 8
4 9
2 5
5 11
7 13
10 4
11 15
12 5
14 7
6
6 11
10 9
2 6
7 6
8 13
8 15
예제 출력 1
2
4
2
1
3
1

Concept

트리 문제는 맞는데, 이 문제를 안 풀어보면 안 그래도 어려운 문제를 더 고통스럽게 풀 것 같다.
조상 탐색을 어떻게 실시할 것인가가 관건이 되겠다. 내 방법은 정말 너무도 무식하게 while문을 두개를 사용하여 시간복잡도가 O($n^2$)인 무시무시한 방법이라, dp를 써야하나..(dp를 쓰기엔 2차원 배열이 [50001][50001]이라 곤란하다..) 고민을 많이 하며 반신반의한 채로 제출을 눌렸으나, 맞아서 더 당황스러웠다.

Comment

#include <iostream>
#include <deque>
#include <queue>
#include <string>
#include <vector>
using namespace std;

vector<int> tree[50001];
int parent[50001];
bool check[50001];

void findfirstParent(int n) {              // n은 시작 노드
    check[n] = true;

    for (int i = 0; i < tree[n].size(); i++) {
        int idx = tree[n][i];       
        if (check[idx] == true) continue;
        parent[idx] = n; 
        findfirstParent(idx);
    }
}


void common(int a, int b) { 
    // a와 b가 같을 경우
    if (a == b) {
        cout << a << endl;
        return;
    }
    // 다르다면
    else {
        int aAnc = a;   // ancestor of a
        int bAnc;       // ancestor of b
        int count1 = 0; // a를 일단 고정후 b를 전체 탐색했을 때 탐색개수 카운트
        int mem1 = -1;  // 조상을 탐색하여 답을 찾았을 때 그 노드값을 저장하는 변수
        bool isfound = false;
        while (!isfound) { // a 조상 탐색
            bAnc = b;
          
            if (aAnc == bAnc) {
                mem1 = bAnc;
                isfound = true;
            }

            while (!isfound && bAnc != 1) { // b조상 탐색
                bAnc = parent[bAnc];
                count1++;
                if (aAnc == bAnc) {
                    mem1 = bAnc;
                    isfound = true;
                }
            }
            if (aAnc == 1) break;
            aAnc = parent[aAnc];
            count1++;

        }



        bAnc = b;
        int count2 = 0; // b를 일단 고정후 a를 전체 탐색
        int mem2 = -1;
        isfound = false;
        while (!isfound) { // b 조상 탐색
            aAnc = a;
            
            if (aAnc == bAnc) {
                mem2 = aAnc;
                isfound = true;

            }


            while (!isfound && aAnc != 1) { // a 조상 탐색
                aAnc = parent[aAnc];
                count2++;
                if (aAnc == bAnc) {
                    mem2 = aAnc;
                    isfound = true;
                }
            }

            if (bAnc == 1) break;
            bAnc = parent[bAnc];
            count2++;

        }

        if (mem1 == -1 || mem2 == -1) { 
            if (mem1 == -1) cout << mem2 << endl;
            else cout << mem1 << endl;
        }
        else { //카운트가 최소가 되는 노드를 출력해야 함.
            if (count1 < count2) cout << mem1 << endl;
            else cout << mem2 << endl;
        }
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }

    findfirstParent(1);

    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        common(a, b);
    }

}

Comment

이게 되네;;
LCA 2를 통해 다시봐야 할 문제