반응형

https://www.acmicpc.net/problem/3584

 

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

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

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 읽어 보고 오시는 것을 추천드립니다!

https://rudalsd.tistory.com/95

 

[ 자료구조 ] 희소 배열(Sparse Table)

1. 희소 배열(Sparse Table) - 배열 원소의 개수가 무조건 배열의 length 값보다 작은 배열 - 희소 배열은 배열의 원소 위치가 연속적이지 않은 배열 2. 희소 배열 만들기 보통 5번 노드에서 1번 노드까지

rudalsd.tistory.com

 

1. 입력받은 트리를 통해서 루트를 level 1, 이후 자식으로 넘어갈 때마다 level을 1씩 늘려나가면서 각 노드의 level을 저장합니다.

 

2. arr[ N ][ i ]에서 N은 노드의 번호, i는 $2^{i}$번 째 부모를 나타냅니다.

 

3. 입력받은 두 수의 level을 맞춰줍니다.

 

4. 만약 두 수가 같지 않다면 두 수가 같을 때까지 level을 낮춰줍니다.

 

5. 마지막에 그 수를 출력합니다.

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<iostream>
#include<vector>
#include<cstring>
#include<cmath>
 
using namespace std;
 
int N;
int arr[10001][14];
int level[10001];
vector<int> list[10001];
 
void dfs(int num, int lv) {
    level[num] = lv;
    for (auto next : list[num]) {
        dfs(next, lv + 1);
    }
}
 
int find(int A, int B) {
    int ret = 0;
 
    if (level[A] > level[B]) {
        int temp = A;
        A = B;
        B = temp;
    }
 
    int size = ceil(log2(N));
 
    if (level[A] != level[B]) {
        for (int i = size - 1; i >= 0; i--) {
            int next = arr[B][i];
            if (next == 0) continue;
            if (level[A] < level[next]) {
                B = next;
            }
        }
 
        B = arr[B][0];
    }
    
    if (A != B) {
        for (int i = size - 1; i >= 0; i--) {
            int pa = arr[A][i];
            int pb = arr[B][i];
 
            if (pa != pb) {
                A = pa;
                B = pb;
            }
        }
 
        A = arr[A][0];
    }
 
    return A;
}
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        scanf("%d", &N);
 
        int size = ceil(log2(N));
        
        memset(arr, 0, sizeof(arr));
        
        for (int i = 1; i <= N; i++) {
            list[i].clear();
        }
 
        for (int i = 0; i < N - 1; i++) {
            int A, B;
            scanf("%d %d", &A, &B);
 
            arr[B][0] = A;
            list[A].push_back(B);
        }
 
        int root = 0;
 
        for (int i = 1; i <= N; i++) {
            if (arr[i][0] == 0) {
                root = i;
                break;
            }
        }
 
        dfs(root, 1);
 
        for (int i = 1; i < size; i++) {    //희소 배열
            for (int j = 1; j <= N; j++) {
                int next = arr[j][i - 1];
                arr[j][i] = arr[next][i - 1];
            }
        }
 
        int A, B;
        scanf("%d %d", &A, &B);
 
        printf("%d\n", find(A, B));
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 1774번 - 우주신과의 교감 (C++)  (0) 2022.11.20
[ 백준 ] 10282번 - 해킹 (C++)  (0) 2022.11.19
[ 백준 ] 5529번 - 저택 (C++)  (0) 2022.11.17
[ 백준 ] 16933번 - 벽 부수고 이동하기 3 (C++)  (0) 2022.11.16
[ 백준 ] 11758번 - CCW (C++)  (0) 2022.11.15

+ Recent posts

티스토리툴바