백준 11438번 LCA2
< 백준 11438번 LCA2 - 마포 코딩박 >
사용한 알고리즘: LCA (최소공통조상)
LCA 를 구현할 줄 알아야 풀 수 있는 문제였습니다.
강산님 블로그 https://blog.naver.com/kks227/220820773477 를 많이 참고하여 풀었습니다. LCA 에 대한 자세한 설명이 있으니 참고하시면 좋을 것 같습니다.
풀이 방법은 다음과 같습니다.
( 사실 LCA 구현법입니다. )
(1) (코드 6~7)
'parent[i][k] : i의 2^k 번째 조상' 라고 설정해줍니다.
(2) (코드 13~22, 36~37)
depth[0]=0 으로 설정하고 각 노드들의 depth를 정하며 트리를 구성합니다.
이때 parent[i][0] 는 바로 위 부모이므로 이를 설정해줍니다.
(3) (코드 39~45)
parent[i][0] 를 설정 해 둔 것을 바탕으로 2^k 번째 부모들을 구해줍니다.
(4) (코드 47~79)
입력으로 두 노드 a, b 를 받으면, 높이를 맞춰 준 후
(이때 a==b가 되면 그 노드가 공통 조상입니다.),
최대 조상 (2^17) 부터 둘의 조상을 비교하면서 내려오며, 둘의 2^k 번째 조상이 다른 경우 해당 위치로 a, b 를 각각 재조정해줍니다.
과정이 끝난 후 a, b 는 같은 부모 밑에 있게 됩니다. 이는 찾고자 하는 최소공통조상입니다.
LCA 구현의 대표적인 문제였습니다.
사용한 알고리즘: LCA (최소공통조상)
LCA 를 구현할 줄 알아야 풀 수 있는 문제였습니다.
강산님 블로그 https://blog.naver.com/kks227/220820773477 를 많이 참고하여 풀었습니다. LCA 에 대한 자세한 설명이 있으니 참고하시면 좋을 것 같습니다.
풀이 방법은 다음과 같습니다.
( 사실 LCA 구현법입니다. )
(1) (코드 6~7)
'parent[i][k] : i의 2^k 번째 조상' 라고 설정해줍니다.
(2) (코드 13~22, 36~37)
depth[0]=0 으로 설정하고 각 노드들의 depth를 정하며 트리를 구성합니다.
이때 parent[i][0] 는 바로 위 부모이므로 이를 설정해줍니다.
(3) (코드 39~45)
parent[i][0] 를 설정 해 둔 것을 바탕으로 2^k 번째 부모들을 구해줍니다.
(4) (코드 47~79)
입력으로 두 노드 a, b 를 받으면, 높이를 맞춰 준 후
(이때 a==b가 되면 그 노드가 공통 조상입니다.),
최대 조상 (2^17) 부터 둘의 조상을 비교하면서 내려오며, 둘의 2^k 번째 조상이 다른 경우 해당 위치로 a, b 를 각각 재조정해줍니다.
과정이 끝난 후 a, b 는 같은 부모 밑에 있게 됩니다. 이는 찾고자 하는 최소공통조상입니다.
LCA 구현의 대표적인 문제였습니다.
아.... 저는 자꾸 틀렸다고 나오네요.
답글삭제혹시, 아래 제 코드의 어디에서 잘못되었는지 한번 봐주실 수 있을까요? ㅠ ㅠ
#include
#include
#include
#include
#include
using namespace std;
#define NMAX 100002
vector Edge[NMAX];
int Parent[20][NMAX];
int depth[NMAX];
int N, M;
int getLCA(int n1, int n2)
{
if (depth[n1] > depth[n2])
swap(n1, n2);
int mx = log2(N) + 1;
for (int i = mx; i >= 0; i--)
{
if (depth[n2] - depth[n1] >= (1 << i))
{
n2 = Parent[i][n2];
}
}
if (n1 == n2)
return n1;
for (int i = mx; i >= 0; i--)
{
if (Parent[i][n1] != Parent[i][n2])
{
n1 = Parent[i][n1];
n2 = Parent[i][n2];
}
}
return Parent[0][n1];
}
int main()
{
freopen("013_백준_11438_LCA 2.txt", "r", stdin);
scanf("%d", &N);
//Init
for (int i = 1; i <= N; i++)
{
Parent[0][i] = -1;
}
for (int i = 0; i < N - 1; i++)
{
int s, e;
scanf("%d %d", &s, &e);
Edge[s].emplace_back(e);
Edge[e].emplace_back(s);
}
queue qu;
qu.emplace(1);
Parent[0][1] = 0;
while (!qu.empty())
{
int cn = qu.front();
qu.pop();
for (auto& nn : Edge[cn])
{
if (Parent[0][nn] == -1)
{
Parent[0][nn] = cn;
depth[nn] = depth[cn] + 1;
qu.emplace(nn);
}
}
}
int mx = log2(N) + 1;
for (int i = 1; i <= N; i++)
{
for (int k = 1; k < mx; k++)
{
int par = Parent[k - 1][i];
Parent[k][i] = Parent[k - 1][par];
}
}
scanf("%d", &M);
for (int i = 0; i < M; i++)
{
int u, v;
scanf("%d %d", &u, &v);
printf("%d\n", getLCA(u, v));
}
return 0;
}