백준 11437 - LCA, LCA2 (C++)

 

문제 이름부터 나와있듯이 LCA알고리즘을 사용하여 푸는 문제이다.

LCA알고리즘에 관한 이해가 없다면, 찾아보고 오는 것을 추천한다.

아래 링크는 본인이 작성해놓은 LCA알고리즘에 대한 설명이다. 

 

알고리즘 - LCA (최소 공통 조상 탐색) (tistory.com)

알고리즘 - LCA (최소 공통 조상 탐색)

 

 

문제는 이러하다.

이러한 트리가 있다고 했을 때, 두 노드가 주어진다면 그 둘의 공통된 조상중 가장 가까운 조상(최소 공통 조상)은 누구인가를 구하는 것이다. 위 그림처럼 15와 6이 입력으로 주어졌다고 가정해보자.

 

15의 조상은 15, 11, 5, 2, 1이 있을 것이다.

6의 조상은 6, 2, 1이 있을 것이다.

 

두 노드의 조상들중 공통된 조상은 2, 1이고 둘 중 노드에 더 가까운 조상은 2이다.

즉, 위 그림에서 파란색으로 칠해진 노드가 최소 공통 조상이 되는 것이다.

 

이 최소 공통 조상을 구하는 알고리즘이 LCA알고리즘이고, 알고리즘을 알고 있다면 그대로 적용해서 풀면 된다. 

 

처음에 헷갈렸던 것중 하나가 LCA알고리즘에선 조상 노드에 본인이 포함된다는 것이다.

두 노드가 같다면, 두 노드의 부모 노드를 출력하는 것이 아니라 두 노드 자체를 출력하면 된다.

예를 들어, 15와 15를 입력받는다면 최소 공통 조상은 그 노드의 부모인 11이 아니라, 15이다.

 

아래는 플래티넘 5단계에 LCA2라는 문제가 있는데,  그에 대한 스포내용이다.

플래티넘 5단계에 LCA2라는 문제가 있는데, 이는 완벽히 동일한 문제라 아래에 나오는 코드 그대로 복사해서 LCA2문제에 제출해도 정답이 나온다. LCA알고리즘은 선형탐색으로 조상을 찾는 방법이 있고, 2의 지수를 활용하여 탐색하는 방법이 있다. 아마도 LCA는 선형탐색으로 푸는 문제이고 LCA2는 2의 지수를 활용하여 시간복잡도를 낮춰서 푸는 문제일 것이다. 본인은 이 문제를 2의 지수를 활용하여 풀었기 때문에 코드를 그대로 복붙했음에도 LCA2 문제를 통과하였다.

 

풀이 코드

---

 

std::cin >> NumOfNode;
MaxExponent = (int)floor(log2(NumOfNode));

 

먼저, 노드가 몇개인지 입력을 받았다.

이후 요상한 수식이 나왔는데, LCA알고리즘은 2의 지수를 기반으로 탐색한다.

저 MaxExponent는 최대 지수가 몇인지를 구한 것이다.

 

예를 들어, 노드가 5만개가 있다고 하자.

가장 말단 노드에서 루트 노드까지 가는데 최대 2^16 (65536) 이상은 요구되지 않는다.

즉, 배열에 16이상의 지수는 저장할 필요가 없기 때문에, MaxExponent를 구한 뒤 그 값에 맞게 배열을 조정하였다.

50000을 넣으면 MaxExponent는 15가 나온다. (2^15 < 50000 < 2^16)

 

for (int i = 1; i < NumOfNode; i++)
{
	int Start = 0;
	int End = 0;

	std::cin >> Start >> End;

	Links[Start].push_back(End);
	Links[End].push_back(Start);
}

Depth.resize(NumOfNode + 1);
Ancestor.resize(NumOfNode + 1, std::vector<int>(MaxExponent + 1, 0));

Depth[0] = -1;

 

이후 연결된 노드를 모두 입력받아 벡터에 저장하였다.

 

LCA알고리즘에선 노드의 깊이와 조상 노드를 알아야 하기 때문에, 이 것을 저장해줄 벡터 또한 resize해주었다.

 

그리고 마지막 줄을 보면 Depth[0] = - 1로 해주었는데, 그 이유는 1번 노드 (루트 노드)의 깊이를 0으로 맞추기 위해서다.

뒤의 코드에 나오겠지만, 현재 노드의 깊이 = 부모 노드의 깊이 + 1로 계산하고 있다.

 

만약, Depth[0] 을 다른 값으로 저장하면 루트 노드에 대해서만 예외처리가 필요하지만, Depth[0] = - 1 로 세팅하면

Depth[1] = Depth[0] + 1 = 0; 이 되므로 예외처리 없이 1번 노드의 깊이를 0으로 맞출 수 있다.

 

Tree(1, 0);

 

이후, Tree를 만들어주는 Tree라는 함수를 실행해주었다.

Tree함수의 내부를 보자.

void Tree(int _CurNode, int _Parent)
{
    Depth[_CurNode] = Depth[_Parent] + 1;
    Ancestor[_CurNode][0] = _Parent;
    
    for (int i = 1; i <= MaxExponent; i++)
    {
        //2^(i - 1) 번째 조상
        int IndexAncestor = Ancestor[_CurNode][i - 1];
        Ancestor[_CurNode][i] = Ancestor[IndexAncestor][i - 1];
    }
    
    int LinkSize = Links[_CurNode].size();
    
    for (int i = 0; i < LinkSize; i++)
    {
        int NextNode = Links[_CurNode][i];
        if (NextNode != _Parent)
        {
            Tree(NextNode, _CurNode);
        }
    }
}

 

인자로는 현재 노드와 부모 노드를 받고있다.

 

함수가 실행되면, 먼저 깊이를 갱신해준다. 위에서 말했듯이 현재 노드의 깊이 =  부모 노드의 깊이 + 1로 갱신해준다.

조상또한 맞춰준다. Ancestor[x][y] 가 의미하는 것은 x의 2^y 번째 조상이다.

y가 0이라면 바로 위의 부모를 의미하는 것이기 때문에 Ancestor[_CurNode][0]에 부모 노드를 저장해 주었다.

 

그 이후 반복문을 돌며 2^i 번쨰의 조상을 저장하고 있다.

반복문 내부으 코드가 이해되지 않을 수도 있는데, 어렵지 않다.

 

 

해당 그림을 보자.

9번 노드의 입장에서 생각해보자

2^0번 조상은 4번 노드이며, 2^1번 조상은 2번 노드이다.

 

여기서, 2^1번 조상인 2번 노드는 9번 노드에서 2^1번을 위로 올라간 것이지만 동시에 9번 노드의 2^0번 조상에서 2^0번만큼 이동한 노드이다.

 

지수가 확장되어도 마찬가지이다.

 

2^i번 조상 = 2^(i - 1)번 조상의 2^(i-1)번 조상

이라는 점화식을 세워볼 수 있다.

 

Tree함수는 (1,0)을 시작으로 DFS를 돌며 트리를 구성할 것이다.

즉, 깊이가 상대적으로 깊은 노드라면, 그 노드의 조상노드들은 이미 본인의 조상노드를 모두 저장하고 있을 것이다.

그렇기 때문에, 조상노드에 저장된 조상노드들을 그대로 가져와서 배열에 저장할 수 있는 것이다.

 

이렇게, 현재 노드의 조상노드를 배열에 모두 기록하였다면 DFS를 돌며 다른 노드를 모두 탐색해주면 된다.

단, 연결된 노드가 부모노드 (2^0번째 조상)인 경우는 예외처리를 하여 탐색하지 않도록 해야한다.

 

Tree함수가 종료되면, 조상 노드를 저장하는 배열과 깊이를 저장하는 배열이 모두 세팅되었을 것이다.

이제 공통 조상을 탐색하기만 하면 된다.

 

int First = 0;
int Second = 0;
std::cin >> First >> Second;

if (Depth[First] != Depth[Second])
{
	//더 깊이가 깊은 곳을 First로 맞춰주기.
	if (Depth[First] < Depth[Second])
	{
		std::swap(First, Second);
	}

	for (int j = MaxExponent; j >= 0; j--)
	{
		if (Depth[Second] <= Depth[Ancestor[First][j]])
		{
			First = Ancestor[First][j];
		}
	}
}

 

먼저, 입력된 두 노드에 대해 깊이가 같지 않다면 맞춰주는 작업을 해야한다.

깊이가 더 깊은 노드를 얕은 노드에 맞춰줄 것이기 때문에 First를 두 노드중 깊이가 더 깊은 노드로 바꿔주자.

 

이후, 최대 지수부터 차례차례 내려오며 깊이를 비교해주자.

First의 조상 노드중 second와 깊이가 같은 노드를 찾는 것이다.

 

2^j번째 조상으로 이동했는데도 Second보다 깊이가 깊다면, 2^j번째 조상으로 이동해준다.

이후 계속 2^j번째 조상으로 옮겨가며 Second의 깊이와 같아질 때까지 반복문을 돌면 된다.

 

이론적으로 모든 수는 2의 지수의 합으로 표현할 수 있기 때문에 j가 0이 되기 전까진 반드시 깊이가 같은 조상 노드를 찾을 수 있다.

 

int LCA = 0;

if (First == Second)
{
    LCA = First;
}
else
{
    for (int j = MaxExponent; j >= 0; j--)
    {
        if (Ancestor[First][j] != Ancestor[Second][j])
        {
            First = Ancestor[First][j];
            Second = Ancestor[Second][j];
        }

        LCA = Ancestor[First][j];
    }
}

Answers[i] = LCA;

 

 

깊이를 맞춰주었다면, 이제 동일하게 움직이면서 조상을 탐색하면 된다.

먼저, 깊이를 맞추고 났더니 First와 Second가 같다면?

 

 

이런 트리였다면, 9와 2에 대해 깊이를 맞추어주면 First ==2 , Second == 2 가 될 것이다.

두 노드의 번호가 같다면, 그 자체가 최소공통조상노드이다.
(위에서도 말했지만, LCA알고리즘에선 본인도 조상노드에 포함한다.)

 

즉, First == Second라면 그냥 First나 Second중 아무거나 출력하면 된다.

 

둘이 다르다면, 깊이를 맞춰주던 때와 똑같이 위로 2^j번씩 이동하며 조상노드를 탐색하면 된다.

만약 이동하면서 두 노드의 조상노드가 같아진다면, 해당 노드는 공통 조상 노드이다.

 

하지만 우리가 찾고자 하는 건, 최소 공통 조상 노드이므로 두 노드의 조상노드가 다를 때만 움직여야 한다.

이 트리에서 봤을 때, 9와 12의 공통 조상 노드는 2와 13이다.

두 노드의 조상이 같은 경우를 탐색하게 되면 2와 13을 모두 탐색하게 될 것이고 둘중 무엇이 최소 공통 조상인지 구별할 수가 없다.

 

그렇기 때문에, 공통조상인 2와 13까지 올라가는 것이 아니라, 공통조상의 직전까지만 올라가도록 하는 것이다.

예를 들어, 9->4까지 올라가고 12->5까지 올라갔다면 그 다음은 두 노드의 조상이 같아서 움직일 수가 없다.

 

이렇게 움직일 수 없을 정도로 조상의 앞까지 갔을 때, 4의 부모 혹은 5의 부모가 그대로 최소 공통 조상 노드가 되는 것이다.

 

지속적으로 First의 부모 혹은 Second의 부모를 저장하다가 반복문을 탈출하면 저장된 값을 출력하면 된다.

 

for (int i = 0; i < Answers.size(); i++)
{
    std::cout << Answers[i] << "\n";
}

 

테스트 케이스에 대한 값을 모두 저장해뒀다가 한 번에 출력해주었다.

 

 

 

LCA알고리즘을 알고 있다면, 그대로 적용해서 풀어보면 된다.

역시 코테는 알고리즘을 많이 아는 것이 최고다. 응용력, 사고력도 물론 중요하지만 간단한 문제임에도 알고리즘을 몰라서 못풀거나 복잡하고 어렵게 풀어야 하는 경우도 많기 때문이다.

문제를 많이 풀어보는 것도 좋겠지만, 다양하게 풀어보도록 하자.