1248. 공통조상

Code Battle (`23 동계 대학생 S/W 알고리즘 특강 기초학습 문제)

본 게시글은 개인 학습 용도로 작성한 게시글입니다.
(문제 출처: SW Expert Academy)

이진 트리에서 임의의 두 정점의 가장 가까운 공통 조상 찾기 + 서브 트리 크기 구하기.
$V$개의 정점과 $E$개의 간선이 주어진다.
공통 조상을 찾을 두 노드가 주어질 것이므로, 그들의 조상을 거슬러 올라가며 비교할 것이다. 따라서 각 노드에는 그들의 부모 정보가 있어야 한다. 비교에는 $O(log{V})$ 시간이 걸린다. (최악의 경우 $O(V)$)
어떤 노드를 루트로 하는 서브트리의 크기를 구해야 한다. 각 노드는 그 들의 자식에 대한 정보를 담지 않을 것이므로 트리 순회를 통해 직접 크기를 구하는 것은 불가능하다. 대안으로, 각 노드에 서브 트리 크기를 기록해 두고, 자식노드와 부모노드를 연결 할 때 부모의 서브트리 크기를 갱신해주는 방법을 사용하여 풀이한다. 갱신하는 데에는 $O(Elog{V})$ 시간이 걸린다. (최악의 경우, $O(EV)$)
매 테스트 케이스마다 각 노드별 부모와 서브트리 크기를 초기화하는데 $O(V)$의 시간이 걸린다.
종합하면 각 테스트 케이스 별 시간 복잡도는 $O(V+Elog{V})$ ~ $O(EV)$

#include <iostream>

#define MAX_V 10000

using namespace std;

struct Node {
	int subtreeSize;
	Node* parent;
};

Node nodes[MAX_V+1];

// O(log(V)) ... or O(V) in worst case.
static Node* findMostCommonAncestor(Node* nodeX, Node* nodeY) {
	int depthX = 0;
	int depthY = 0;
	for (Node* curX = nodeX; curX != nullptr; curX = curX->parent) {
		depthX++;
	}
	for (Node* curY = nodeY; curY != nullptr; curY = curY->parent) {
		depthY++;
	}
	while (depthX > depthY) {
		nodeX = nodeX->parent;
		depthX--;
	}
	while (depthX < depthY) {
		nodeY = nodeY->parent;
		depthY--;
	}
	while (nodeX != nullptr && nodeY != nullptr) {
		if (nodeX == nodeY) {
			return nodeX;
		}
		nodeX = nodeX->parent;
		nodeY = nodeY->parent;
	}
	return nullptr;
}

int getNumOf(Node* node) {
	return (int) ((size_t) node - (size_t) nodes) / sizeof(Node);
}

static void solve(int test_case_no)
{
	int V, E, x, y, parent, child;
	Node *currentNode, *parentNode;
	cin >> V >> E >> x >> y;
	// O(V)에 트리 초기화
	for (int v = 1; v <= V; v++) {
		currentNode = nodes + v;
		currentNode->subtreeSize = 1;
		currentNode->parent = nullptr;
	}
	// O(ElogV)에 트리 구축
	for (int i = 0; i < E; i++) {
		cin >> parent >> child;
		currentNode = nodes + child;
		parentNode = nodes + parent;
		currentNode->parent = parentNode;
		while (parentNode != nullptr) {
			parentNode->subtreeSize += currentNode->subtreeSize;
			parentNode = parentNode->parent;
		}
	}
	Node *mca = findMostCommonAncestor(nodes+x, nodes+y);
	printf("#%d %d %d\n", test_case_no, getNumOf(mca), mca->subtreeSize);
}

int main(int argc, char **argv)
{
	int T;
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> T;
	for (int test_case_no = 1; test_case_no <= T; ++test_case_no)
	{
		solve(test_case_no);
	}
	return 0;
}