(백준/ C++) 11438 - LCA 2 / 효율적인 LCA(+sparse table)

11438번: LCA 2 (acmicpc.net)

11438번: LCA 2

희소 테이블에 대해 모른다면 풀기 어려운 문제 일거 같습니다.

풀기전에 희소 테이블로 워밍업을 하고 천천히 풀어보자. 아래 주소는 희소 테이블에 관한 문제입니다.

[Algorithm/ Sparse Table (희소테이블)] 백준 17435번과 함께 (tistory.com)

[Algorithm/ Sparse Table (희소테이블)] 백준 17435번과 함께

 

다시 LCA 2로 돌아와서 문제를 보자. LCA와 다른 점은 주어지는 정점의 수와 노드의 쌍 입니다. 즉 이전에 풀었던거보다 더 효.율.적.으.로 풀어야 합니다.

LCA1

LCA2

LCA2를 깊이를 맞춘 후 조상이 같을 때까지 올라가게 되면 시간 복잡도는
쿼리 횟수 M * 1회 연산시 시간 N = O (MN)
최대 M(100,000) * N(100,000) = 10,000,000,000 이 됩니다.. 시간초과 !! 시간초과!! 

문제에서 주어진 예제를 가지고 효.율.적.으.로 천천히 풀어봅시다. 

첫번째, 주어지는 노드의 쌍의 깊이를 비교해야 합니다! 왜냐하면 깊이를 맞춰주고 Root 방향으로 함께 올라가면서 가장 가까운 조상을 찾아야 효율이 좋기 때문입니다. 그러면 각각의 노드의 깊이를 알아야 겠죠? 일단 깊이를 저장해 줍니다. DFS로! 

• vector<int> gLink[100'101]; - 연결되어 있는 노드를 벡터에 쏙쏙 넣어줬습니다. 
• int gDepth[100'001]; - 방문처리 배열을 하나 더 만들고 싶지 않아서 방문 하지 않을 때는 모두 -1로 초기화 해줬습니다.  memset(gDepth, -1, sizeof(gDepth)); (헤더: memory.h) 

void DFS(int pIdx, int pDepth)
{
	if(gDepth[pIdx] == -1)
		gDepth[pIdx] = pDepth;


	for (size_t i = 0; i < gLink[pIdx].size(); ++i)
	{
		int aNext = gLink[pIdx][i];

		if (gDepth[aNext] == -1)
			DFS(aNext, pDepth + 1);
		else
			continue;
	}
}

코드를 실행한 결과 입니다. 제가 위에 그려놓은 깊이와 동일하게 잘 들어 간 걸 확인 할 수 있습니다.  

 

두번째, 2의 제곱근으로 각각 노드의 부모를 저장해줍니다. 비교할 최초의 테이블이 있어야하기 때문에 초기 세팅을 해주고 나머지를 쫘~~악 해줍니다. 초기 세팅은 현재 노드의 부모를 저장하고 있을테니 아래 표 처럼 저장이 될겁니다.

초기 세팅 다음 코드는 

 

15의 부모가 저장되어 있는 gSparseTable [0][15]에서 값(x:11)을 받아와 다시 gSparseTable [0][값(x:11)]에서 값(y: 5)을 받으면 이 값y는 15의 할머니& 할아버지가 됩니다.

 

void LCA(int pN)
{
	// 초기 세팅 ------------------------------------
	for (int i = 1; i <= pN; ++i)
	{
		for (size_t j = 0; j < gLink[i].size(); ++j)
		{
			if (gDepth[i] < gDepth[gLink[i][j]])
			{
				gSparseTable[0][gLink[i][j]] = i;
			}
			else
			{
				gSparseTable[0][i] = gLink[i][j];
			}
		}
	}

	// -----------------------------------------------
	for (int i = 1; i < st; ++i)
	{
		for (int j = 1; j <= pN; ++j)
		{
			int temp = gSparseTable[i - 1][j];
			gSparseTable[i][j] = gSparseTable[i - 1][temp]; 
		}
	}	
}

 

세번째, 깊이를 일치 시켜 줍니다. 

int aFindDepth (int pParm, int pDiff)
{
	int cur = pParm;
	for (int i = 0; i < st; ++i)
	{
		if (pDiff & (1 << i))
		{
			cur = gSparseTable[i][cur];
		}
	}
	return cur;
};

 

자... 마지막 깊이를 맞췄는데 아직 최소 공통 조상을 만나기 전이면 같이 사이 좋게 올라가 줍니다.

int FindLCA(int pA, int pB, int pN)
{
	int H = 0; 

	while (pN > 1)
	{
		pN /= 2; 
		H++;
	}

	if (pA != pB)
	{
		for (int i = H; i >= 0; --i)
		{
			if(gSparseTable[i][pA]!=0 && gSparseTable[i][pA]!= gSparseTable[i][pB])
			{
				pA = gSparseTable[i][pA];
				pB = gSparseTable[i][pB];
			}
		}

		return gSparseTable[0][pA];
	}
	else
	{
		return pA;
	}
}

 

총 합 코 드 ... 수고 하셨습니다 ~ 

/hide

#include <iostream>
#include <vector>
#include <memory.h>
using namespace std;


constexpr int st = 21;

vector<int> gLink[100'101];
int gSparseTable[st][100'001];
int gDepth[100'001];

void DFS(int pIdx, int pDepth)
{
	if(gDepth[pIdx] == -1)
		gDepth[pIdx] = pDepth;


	for (size_t i = 0; i < gLink[pIdx].size(); ++i)
	{
		int aNext = gLink[pIdx][i];

		if (gDepth[aNext] == -1)
			DFS(aNext, pDepth + 1);
		else
			continue;
	}
}

void LCA(int pN)
{
	// 초기 세팅 ------------------------------------
	for (int i = 1; i <= pN; ++i)
	{
		for (size_t j = 0; j < gLink[i].size(); ++j)
		{
			if (gDepth[i] < gDepth[gLink[i][j]])
			{
				gSparseTable[0][gLink[i][j]] = i;
			}
			else
			{
				gSparseTable[0][i] = gLink[i][j];
			}
		}
	}

	// -----------------------------------------------
	for (int i = 1; i < st; ++i)
	{
		for (int j = 1; j <= pN; ++j)
		{
			int temp = gSparseTable[i - 1][j];
			gSparseTable[i][j] = gSparseTable[i - 1][temp]; 
		}
	}	
}

int aFindDepth (int pParm, int pDiff)
{
	int cur = pParm;
	for (int i = 0; i < st; ++i)
	{
		if (pDiff & (1 << i))
		{
			cur = gSparseTable[i][cur];
		}
	}
	return cur;
};

int FindLCA(int pA, int pB, int pN)
{
	int H = 0; 

	while (pN > 1)
	{
		pN /= 2; 
		H++;
	}

	if (pA != pB)
	{
		for (int i = H; i >= 0; --i)
		{
			if(gSparseTable[i][pA]!=0 && gSparseTable[i][pA]!= gSparseTable[i][pB])
			{
				pA = gSparseTable[i][pA];
				pB = gSparseTable[i][pB];
			}
		}

		return gSparseTable[0][pA];
	}
	else
	{
		return pA;
	}
}

int main(void)
{
	ios_base::sync_with_stdio(false); 
	cin.tie(0); cout.tie(0); 

	memset(gDepth, -1, sizeof(gDepth));

	// root = 1 
	int n; cin >> n; 

	for (int i = 0; i < n - 1; ++i)
	{
		int a, b; 
		cin >> a >> b; 
		gLink[a].push_back(b); 
		gLink[b].push_back(a);
	}

	DFS(1, 0);
	LCA(n);

	int m; cin >> m; 

	for (int i = 0; i < m; ++i)
	{
		int a, b; 
		cin >> a >> b;

		int aDiff = 0; 
		
		if (gDepth[a] != gDepth[b])
		{
			if (gDepth[a] < gDepth[b]) // a가 b보다 위에 있다. 
			{
				aDiff = gDepth[b] - gDepth[a];
				b = aFindDepth(b, aDiff);
			}
			else
			{
				aDiff = gDepth[a] - gDepth[b];
				a = aFindDepth(a, aDiff);
			}
		}

		cout << FindLCA(a, b, n) << "\n";
	}
	return 0;
}