11437 LCA

์•Œ๊ณ ๋ฆฌ์ฆ˜ (BFS, LCA)

1. ํŠธ๋ฆฌ๋งŒ๋“ค๊ธฐ
	1. check ๋ฐฐ์—ด์„ ๋งŒ๋“ค๊ณ , 1๋ฒˆ ๋…ธ๋“œ๋งŒ true ํ‘œ์‹œํ•จ
	2. ์ •์  ์Œ์ด ๋“ค์–ด์™”์„ ๋•Œ, ๋‘˜์ค‘์— check ํ‘œ์‹œ๋œ ๊ฒƒ์ด A, ์•ˆ๋œ ๊ฒƒ์ด B๋ผ๊ณ  ํ• ๋•Œ, B์˜ ๋ถ€๋ชจ์—” A๋ฅผ, ๊นŠ์ด์—” A+1์„ ๋„ฃ๊ณ , check[B] ์— true ํ‘œ์‹œํ•จ
	3. true ํ‘œ์‹œ๊ฐ€ ๋๋‚˜๊ณ , B์— ์ธ์ ‘ํ•œ ์ •์ ๋“ค์„ BFS๋กœ ๋๊นŒ์ง€ ๋ฐฉ๋ฌธํ•˜๋ฉด์„œ ๊นŠ์ด๋ฅผ ๋ถ€์—ฌํ•˜๊ณ  check ํ‘œ์‹œํ•จ.
	4. ๋งŒ์•ฝ ๋‘˜ ๋‹ค check์— ํ‘œ์‹œ๊ฐ€ ์•ˆ๋ผ์žˆ์œผ๋ฉด, ๋‘ ์ •์ ์˜ ์ธ์ ‘ํ•œ ์ •์  ๋ฒกํ„ฐ์— ๋‘˜๋‹ค ์ถ”๊ฐ€ํ•œ๋‹ค.
2. LCA ์ฐพ๊ธฐ

	1. log2์˜ ๋ถ€๋ชจ๋ฅผ ์ฐพ๋Š” ๋ฐฉ๋ฒ•์œผ๋กœ ํ’€๋ฉด ์•„์ฃผ ๋น ๋ฅด๊ฒŒ ๊ฐ€๋Šฅ. ํ•˜์ง€๋งŒ, ์ด ๋ฐฉ๋ฒ•์€ ์–ด๋ ต๋‹ค
	2. ๊ฐ„๋‹จํ•˜๊ฒŒ ๋‘ ์ •์  ์ค‘ ๊นŠ์ด๊ฐ€ ๋” ๊นŠ์€ ๊ฒƒ์„ ๋ถ€๋ชจ๋ฅผ ์ฐพ์•„๊ฐ€๋ฉด์„œ ๋œ ๊นŠ์€ ๊ฒƒ๊ณผ ๊นŠ์ด๋ฅผ ๋˜‘๊ฐ™์ด ๋งž์ถค
	3. ๊นŠ์ด๊ฐ€ ๊ฐ™์•„์ง€๋ฉด, ์ •์ ์ด ๊ฐ™์•„์งˆ๋•Œ๊นŒ์ง€ ๋‘˜๋‹ค ๋ถ€๋ชจ๋ฅผ ์ฐพ์•„๊ฐ
		-> 1์ดˆ๋Œ€.

์ฝ”๋“œ

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX_NODE 50001
 
using namespace std;
 
typedef struct Node {
	int depth;
	int parent;
	vector<int> closeNode;
} Node;
Node node[MAX_NODE];
int numOfNode, list[MAX_NODE];
bool check[MAX_NODE];
 
int findLCS(int first, int second);
void makeTree(int root);
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	cin >> numOfNode;
	check[1] = true;
	int temp1, temp2, numOfPair;
 
	for (int i = 0; i < numOfNode-1; i++) {
		cin >> temp1 >> temp2;
		if (check[temp1]) {
			node[temp2].depth = node[temp1].depth + 1;
			node[temp2].parent = temp1;
			check[temp2] = true;
			if(node[temp2].closeNode.size() > 0)
				makeTree(temp2);
		}
		else if (check[temp2]) {
			node[temp1].depth = node[temp2].depth + 1;
			node[temp1].parent = temp2;
			check[temp1] = true;
			if (node[temp1].closeNode.size() > 0)
				makeTree(temp1);
		}
		else {
			node[temp1].closeNode.push_back(temp2);
			node[temp2].closeNode.push_back(temp1);
		}
	}
 
	cin >> numOfPair;
	for (int i = 0; i < numOfPair; i++) {
		cin >> temp1 >> temp2;
		int curResult = node[temp1].depth < node[temp2].depth ? findLCS(temp1, temp2) : findLCS(temp2, temp1);
		cout << curResult << "\n";
	}
}
 
void makeTree(int root) {
	int index = 0, length = 0;
	list[length++] = root;
 
	while (index < length) {
		int cur = list[index++];
		int depth = node[cur].depth + 1;
 
		for (int i = 0; i < node[cur].closeNode.size(); i++) {
			int t = node[cur].closeNode[i];
			if (!check[t]) {
				node[t].depth = depth;
				node[t].parent = cur;
				check[t] = true;
				list[length++] = t;
			}
		}
		node[cur].closeNode.clear();
	}
	return;
}
 
int findLCS(int first, int second) {
	while (node[first].depth != node[second].depth)
		second = node[second].parent;
	while (first != second) {
		first = node[first].parent;
		second = node[second].parent;
	}
	return first;
}