반응형

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

1. LCA 알고리즘 :: http://www.crocus.co.kr/660


이 문제를 풀기 전 위의 개념을 꼭 숙지하고


아래 다양한 문제를 먼저 풀어보는 것을 추천한다.


LCA 연관 문제 :: http://www.crocus.co.kr/search/LCA



참고로 이 문제는 [11438번] LCA2 :: http://www.crocus.co.kr/661와 문제가 동일하다. 


LCA의 가장 기본이 되는 문제이므로 LCA 개념이 없으면 문제를 해결 할 수 없고, 


더 많은 설명을 하기는 위의 링크들로 충분히 설명이 될 듯 하다.









소스 코드 : 


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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <memory.h>
 
#define swap(a,b){int t = a; a = b; b = t;}
#define MAX_NODE 100001
 
using namespace std;
 
// depth :: 노드의 깊이(레벨)
// ac[x][y] :: x의 2^y번째 조상을 의미
int depth[MAX_NODE];
int ac[MAX_NODE][20];
int parent[MAX_NODE];
 
typedef pair<int, int> pii;
vector<int> graph[MAX_NODE];
 
int max_level;
 
void make_tree(int here, int parent)
{
    // here의 깊이는 부모노드깊이 + 1
    depth[here] = depth[parent] + 1;
 
    // here의 1번째 조상은 부모노드
    ac[here][0] = parent;
 
    // MAX_NODE에 log2를 씌어 내림을 해준다.
    max_level = (int)floor(log2(MAX_NODE));
 
    for (int i = 1; i <= max_level; i++)
    {
        // tmp :: here의 2^(i-1)번째 조상
        /*
        즉, ac[here][i] = ac[tmp][i-1]은
        here의 2^i번째 조상은 tmp의 2^(i-1)번째 조상의 2^(i-1)번째 조상과 같다는 의미
        예를들어 i = 3일때
        here의 8번째 조상은 tmp(here의 4번째 조상)의 4번째 조상과 같다.
        i =  4일때 here의 16번째 조상은 here의 8번째 조상(tmp)의 8번째와 같다.
        */
        int tmp = ac[here][i - 1];
        ac[here][i] = ac[tmp][i - 1];
    }
 
    // dfs 알고리즘
    int len = graph[here].size();
    for (int i = 0; i < len; i++)
    {
        int there = graph[here][i];
        if (there != parent)
            make_tree(there, here);
    }
}
 
int main()
{
    int tc, n;
 
    scanf("%d", &tc);
    while(tc--)
    {
        memset(depth, 0, sizeof(depth));
        memset(ac, 0, sizeof(ac));
        memset(parent, 0, sizeof(parent));
        for (int i = 0; i < MAX_NODE; i++)
            graph[i].clear();
 
        scanf("%d", &n);
 
        // 양방향 그래프 형성
        for (int i = 1; i < n; i++)
        {
            int from, to;
            scanf("%d %d", &from, &to);
            graph[from].push_back(to);
            graph[to].push_back(from);
 
            parent[to] = from;
        }
 
        // make_tree에 1,0이 들어가기때문에 0은 -1로 지정
        int root;
        for (int i = 1; i <= n; i++)
            if (parent[i] == 0)
            {
                root = i;
                break;
            }
 
        depth[0] = -1;
 
        // 루트 노드인 1번 노드부터 트리 형성
        make_tree(root, 0);
 
        int a, b;
        scanf("%d %d", &a, &b);
 
        if (depth[a] != depth[b])
        {
            // depth[b] >= depth[a]가 되도록 swap
            if (depth[a] > depth[b])
                swap(a, b);
 
            // b를 올려서 depth를 맞춰준다.
            for (int i = max_level; i >= 0; i--)
            {
                // b의 2^i번째 조상이 a의 depth보다 크거나 같으면 계속 조상을 타고간다.
                if (depth[a] <= depth[ac[b][i]])
                    b = ac[b][i];
            }
        }
 
        int lca = a;
 
        // a와 b가 다르다면 현재 깊이가 같으니
        // 깊이를 계속 올려 조상이 같아질 때까지 반복한다.
        if (a != b)
        {
            for (int i = max_level; i >= 0; i--)
            {
                if (ac[a][i] != ac[b][i])
                {
                    a = ac[a][i];
                    b = ac[b][i];
                }
                lca = ac[a][i];
            }
        }
 
        printf("%d\n", lca);
        
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


반응형
저작자표시 비영리 변경금지

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[13235번] 팰린드롬 (Palindromes)  (0) 2017.06.20
[6081번] Hay Expenses  (0) 2017.06.20
[2110번] 공유기 설치  (0) 2017.06.17
[2204번] 도비의 난독증 테스트  (0) 2017.06.13
[2033번] 반올림  (0) 2017.06.07

티스토리툴바