[백준] 3548번 가장 가까운 공통 조상

3584 가장 가까운 공통 조상

문제

---

루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다.

-두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다.

예를 들어  15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그 중 깊이가 가장 깊은(15와 11에 가장 가까운) 노드는 4 이므로 가장 가까운 공통 조상은 4가 됩니다.

루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성하세요

입력

---

첫 줄에 테스트 케이스의 개수 T가 주어집니다.

각 테스트 케이스마다, 첫째 줄에 트리를 구성하는 노드의 수 N이 주어집니다. (2 ≤ N ≤ 10,000)

그리고 그 다음 N-1개의 줄에 트리를 구성하는 간선 정보가 주어집니다. 한 간선 당 한 줄에 두 개의 숫자 A B 가 순서대로 주어지는데, 이는 A가 B의 부모라는 뜻입니다. (당연히 정점이 N개인 트리는 항상 N-1개의 간선으로 이루어집니다!) A와 B는 1 이상 N 이하의 정수로 이름 붙여집니다.

테스트 케이스의 마지막 줄에 가장 가까운 공통 조상을 구할 두 노드가 주어집니다.

출력

---

각 테스트 케이스 별로, 첫 줄에 입력에서 주어진 두 노드의 가장 가까운 공통 조상을 출력합니다.

---

풀이)

단순히 어떤 노드끼리 연결되었는지 정보를 준 것이 아니라 부모-자식 노드 관계 정보를 준 문제여서

주어진 정보를 이용해 그대로 트리를 만들어 풀면 된다.

과정

1. 트리를 만든다.

(사용하는 배열들)

int parent[i] // i 노드의 부모 노드 번호 저장하는 배열

int depth[i] // i 노드의 트리 내에서의 깊이 저장하는 배열

parent[]배열을 이용해 트리의 루트 노드 번호를 찾고, (루트 노드 번호는 그 노드의 부모 노드 번호와 일치할때의 번호)

그리고 그 루트 노드부터 시작해 dfs로 각 노드들 깊이들을 확인해 depth[]에 저장

ex) 트리 입력 예시

n = 5

(2 3)

(3 4)

(3 1)

(1 5)

(3 5) 일때,

2. 공통 조상을 구할 두 노드의 트리 내 깊이를 확인한다.

     노드가 n1, n2라고 할때 depth[n1] , depth[n2] 확인

3. 두 노드가 같은 깊이를 가질 때까지 한 노드를 그 노드의 부모로 바꿔준다.

4. 깊이가 같아졌을 때 노드 번호가 똑같은지 확인 

                             같은 번호가 아니라면, 두 노드들 모두 같은 번호가 될때까지 각자 부모 노드로 변경.

5. 같은 노드 번호(= 최소 공통 조상)를 출력

코드)

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
 
int n;
vector <int> adj[10001];
int depth[10001];
int parent[10001];
 
void dfs(int node) {
    for (int i = 0; i < adj[node].size(); i++) {
        int next = adj[node][i];
        if (depth[next] == -1) {
            depth[next] = depth[node] + 1;
            dfs(next);
        }
    }
}
int main() {
    int test_case;
    scanf("%d", &test_case);
    while (test_case--)
    {
        scanf("%d", &n);
        int a, b;
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
        for (int i = 0; i < n-1; i++) {
            scanf("%d %d", &a, &b);
            parent[b] = a;
            adj[a].push_back(b);
        }
        int n1, n2;
        scanf("%d %d", &n1, &n2);
 
        for (int i = 1; i <= n; i++) {
            depth[i] = -1;
        }
 
        int root = 1;
        while (true)
        {
            if (root == parent[root]) break;
            root = parent[root];
        }
        depth[root] = 0;
        dfs(root);
        
        if (depth[n1] < depth[n2]) swap(n1, n2);//깊이가 깊은 노드를 n1으로
        
        while (depth[n1] != depth[n2]) //깊이가 같아질때까지
        {
            n1 = parent[n1];
        }
        if (n1 == n2) {
            printf("%d\n", n1);
            continue;
        }
        while (n1 != n2)
        {
            n1 = parent[n1];
            n2 = parent[n2];
        }
        printf("%d\n", n1);
 
        for (int i = 1; i <= n; i++) {
            parent[i] = -1;
            adj[i].clear();
        }
    }
    return 0;
}