1을 루트로 하는 트리가 주어질 때 두 정점의 가장 가까운 공통 조상의 번호를 출력한다.
LCA를 처음 공부할 때 개념을 잡기 좋은 문제라고 한다.
다른 블로그를 돌아다니면서 개념을 익힐 때 왜 깊이를 DFS로 설정해 주는지 의문을 가졌었다.
예제를 직접 노트로 옮겨보니 바로바로 이어져서 입력과 동시에 깊이와 부모를 설정해 줬는데 제출을 하니 바로 시간초과에 걸렸었다.
TC로 들어오는건 꼭 1이 있는 트리에 이어져서 들어오는게 아니라 나눠져 들어오기 때문에 깊이와 부모 설정에 문제가 생겨 높이를 맞추는 과정에서 무한루프에 빠지게 됬었다.
원인을 알고나니 왜 블로그에서 DFS를 이용해서 깊이를 설정해 주는지 이해가 갔다.
vector를 이용해서 인접행렬을 구현하고, 깊이와 부모를 저장할 변수를 따로 지정해 DFS를 통해 부모와 깊이를 설정.
공통 조상을 찾을 두 노드의 높이를 낮은 쪽으로 맞춘 후, 두 노드가 같아질 때 까지 부모노드를 타고 올라방식으로 구현했다.
#include <iostream>
#include <vector>
#include <string.h>
using namespace std;
const int MAX = 50000;
vector<vector<int>> vertex;
int parent[MAX] = { };
int level[MAX] = { };
bool check[MAX];
void balancing(int& node1, int& node2) {
while (level[node1] > level[node2])
node1 = parent[node1];
while (level[node1] < level[node2])
node2 = parent[node2];
}
void setParNLevel(int node) {
check[node] = true;
int edgeCount = vertex[node].size();
for (int i = 0; i < edgeCount; i++) {
int vert = vertex[node][i];
if (!check[vert]) {
parent[vert] = node;
level[vert] = level[node] + 1;
setParNLevel(vert);
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n;
vertex.resize(n);
for (int i = 0; i < n - 1; i++) {
int to, des;
cin >> to >> des;
vertex[to - 1].push_back(des - 1);
vertex[des - 1].push_back(to - 1);
}
setParNLevel(0);
cin >> m;
for (int i = 0; i < m; i++) {
int node1, node2;
cin >> node1 >> node2;
node1--; node2--;
balancing(node1, node2);
while (node1 != node2) {
node1 = parent[node1];
node2 = parent[node2];
}
cout << node1 + 1 << '\n';
}
return 0;
}
2019-04-22 16:46:02에 Tistory에서 작성되었습니다.