링크
https://www.acmicpc.net/problem/11438
11438번: LCA 2
첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정
www.acmicpc.net
해설
이 문제는 DFS와 BFS 모두 사용할 수 있습니다.
그러나 BFS 가 메모리도 적게사용하고 시간도 약간 더 빨라 해설에서는 BFS를 사용하였습니다.
DFS버전이 궁금하시면 >> 깃허브 << 에 올려두었습니다.
골드문제에서는 주로 정적배열만으로 해결이 다 됬었는데 플레티넘으로 넘어가니 동적배열을 사용해야하네요.
2차원 vector 을 이용해서 각 노드별로 연결된 노드들의 숫자를 다 입력해둡니다.
그 후 BFS 를 이용해서 각 노드들의 깊이(depth) 를 구합니다.
골드문제인 11437 LCA 는 그냥 깊이를 맞추고 상승시켜가면서 같은걸 찾으면 되지만
이 문제같은 경우는 훨씬 노드가 많기때문에 O(N) 의 복잡도를 이용하면 시간초과가 나게됩니다.
보통 O(N) 보다 더 낮은 시간복잡도를 가지려면 이분탐색을 이용하는데 여기도 똑같습니다.
PARENT 배열에 각 노드의 2^0 , 2^1 , 2^2 , ... 위의 노드들을 저장해 두고 사용합니다.
이렇게 탐색을 하면 O(log N) 만에 찾을 수 있습니다.
코드를 보시면
PARENT[next][i] = PARENT[PARENT[next][i - 1]][i - 1]위와 같은 코드를 보실 수 있는데
이코드의 의미는 현재 노드의 2^i 위의 부모는 2^(i - 1) 위 부모의 2^(i - 1) 위 부모와 같다는 뜻입니다.
그림과 같이 4 위의 노드는 2위의 노드의 2위 노드 와 같다는 것이죠.
그렇게 모든 2^i 위 노드들을 다 구해두고 입력이 들어올 때 마다 LCA 함수를 이용해서 값을 구해줍니다.
두 값의 깊이를 또 이분탐색을 이용해서 더 얕은것에 맞춰주고 아까 구해뒀던 PARENT 배열을 이용해
LCA 를 찾을 때 까지 이동을 하다가 찾으면 return 하면됩니다.
코드에 모두 구현되어있습니다.
코드
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N, M, DEP[100001], PARENT[100001][18];
bool visit[100001];
vector<vector<int>> LIST;
queue<int> que;
int LCA(int _a, int _b) {
if (DEP[_a] < DEP[_b]) swap(_a, _b);
int looper = 0;
while (DEP[_a] != DEP[_b]) {
++looper;
if ((DEP[_a] - (1 << looper)) < DEP[_b]) {
_a = PARENT[_a][looper - 1];
looper = 0;
}
}
while (_a != _b) {
looper = 1;
while (PARENT[_a][looper] != PARENT[_b][looper])
++looper;
_a = PARENT[_a][looper - 1];
_b = PARENT[_b][looper - 1];
}
return _a;
}
void BFS() {
que.push(1);
while (!que.empty()) {
int now = que.front();
que.pop();
for (int i = 0; i < LIST[now].size(); ++i) {
int next = LIST[now][i];
if (visit[next])
continue;
visit[next] = true;
que.push(next);
DEP[next] = DEP[now] + 1;
PARENT[next][0] = now;
for (int i = 1; i < 18; ++i) {
PARENT[next][i] = PARENT[PARENT[next][i - 1]][i - 1];
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
LIST.resize(N + 1);
for (int i = 0; i < N - 1; ++i) {
int a, b;
cin >> a >> b;
LIST[a].push_back(b);
LIST[b].push_back(a);
}
DEP[1] = 1;
visit[1] = true;
BFS();
cin >> M;
for (int i = 0; i < M; ++i) {
int a, b;
cin >> a >> b;
cout << LCA(a, b) << "\n";
}
return 0;
}'컴퓨터공학 > 백준' 카테고리의 다른 글
| [백준][14003][C++] 가장 긴 증가하는 부분 수열 5 (0) | 2021.07.16 |
|---|---|
| [백준][2252][C++] 줄 세우기 (0) | 2021.07.15 |
| [백준][12015][C++] 가장 긴 증가하는 부분 수열 2 (0) | 2021.07.13 |
| [백준][1707][C++] 이분 그래프 (0) | 2021.07.12 |
| [백준][1717][C++] 집합의 표현 (0) | 2021.07.12 |
