[백준/C++] 11437, 11438. LCA 1,2

문제

https://www.acmicpc.net/problem/11437  -> LCA 1

https://www.acmicpc.net/problem/11438  -> LCA 2

 

주어진 두 노드에 대해 LCA(가장 가까운 공통 조상)을 구하면 되는 문제이다.

1번과 2번의 차이는 노드의 최대 갯수 및 시간 제한의 차이이다. 

LCA2가 훨씬 빡빡하다. 

 

풀이

1. 11437 LCA1번 풀이 

연결된 두 노드 a,b가 N-1개의 줄에 걸쳐서 입력되는데, a,b중에 어떤 노드가 부모노드인지는 입력 받을 때에는 알 수가 없다. 

그래서 처음에는 연결리스트 형태로 저장했다가, 입력을 다 받은 후에 BFS를 통해 루트인 1부터 타고 들어가서 트리구조를 파악할 수 있도록 했다. (각 노드의 부모와, 깊이 저장) 

그리고 LCA를 찾는 알고리즘은, a,b의 깊이가 다르면, 같아질 때 까지 a,b중에 깊이가 깊은 노드를 부모로 갱신시키면서 깊이가 같아지도록 했다. 

그 후에는 두 노드 a,b가 같은 값이 될 때 까지, 한 단계씩 위로 올라오면서 갱신시키는 과정을 거쳤다. 

 

 

2. 11438 LCA2번 풀이 

1번 풀이를 그대로 제출했더니 역시 시간초과가 났다!  

한 가지 다행인건, 세그먼트 트리를 이용하지 않고 DP만으로 해결이 가능하다는 점이었다. 

트리의 구조가 계속 변하는 문제가 아니라서 DP방식을 이용할 수 있는 것 같다. 

parent배열을 2차원으로 만들어서, 각 노드별로 2^i번째의 부모를 parent[n][i]에 저장했다. 

그리고 LCA를 찾는 알고리즘은, 1번과 비슷하지만 2차원으로 만든 parent를 이용해서 더 적은 시간복잡도로 구할 수 있다. 

a와 b의 높이를 같게 만든다음에 한 단계씩 위로 올라가면서 계산하는 과정은 1번과 똑같지만, a와 b의 높이를 같게 만들 때, 1번은 한 단계씩 움직이는 반면에, 2번은 2로 나눠서 반씩 올라가며 구하기 때문에 2번에서 계산 횟수가 줄어들게된다. 

 

 

코드

1번 코드

#include <iostream>
#include <vector>
#include <queue>

#define sc scanf_s
#define maxN 50001
using namespace std;

int N, M;
vector<int> graph[maxN];
int parent[maxN];
int depth[maxN];
bool visited[maxN];

int max_depth = 0;
void BFS(int start) { //부모-자식 구조를 파악하기 위함 
	queue<int> q;
	q.push(start);
	depth[start] = 0;
	visited[start] = 1;
	while (!q.empty()) {
		int temp = q.front();
		q.pop();
		for (int i = 0;i < graph[temp].size();i++) {
			int next = graph[temp][i];
			if (!visited[next]) {
				visited[next] = 1;
				parent[next] = temp;
				depth[next] = depth[temp] + 1;
				if (depth[next] > max_depth) max_depth = depth[next];
				q.push(next);
			}
		}
	}
}
int findCommonParent(int a, int b) {
	int a_d = depth[a];
	int b_d = depth[b];

	while (true) {
		// depth가 다른데 부모가 같을 수는 없음 
		if (a_d > b_d) {
			a_d--;
			a = parent[a];
		}
		else if (a_d < b_d) {
			b_d--;
			b = parent[b];
		}
		else {
			if (a == b) {
				return a;
			}
			a_d--;
			a = parent[a];
			b_d--;
			b = parent[b];
		}
	}
}
int main() {
	sc("%d", &N);
	for (int i = 1;i < N;i++) {
		int a, b;
		sc("%d %d", &a, &b);
		graph[a].push_back(b);
		graph[b].push_back(a);
	}

	// 부모 자식 찾기 
	BFS(1);

	sc("%d", &M);
	for (int i = 0;i < M;i++) {
		int a, b;
		sc("%d %d", &a, &b);
		// 공통조상 찾아 출력
		printf("%d\n", findCommonParent(a, b));
	}
	return 0;
}

2번 코드 

#include <iostream>
#include <vector>
#include <queue>

#define sc scanf_s
#define maxN 100001
#define maxD 18 // 10^5 < 2^17 
using namespace std;

int N, M;
vector<int> graph[maxN];
int parent[maxN][maxD]; // n의 2^d번 째 부모
int depth[maxN];
bool visited[maxN];

int max_depth = 0;
void BFS(int start) { //부모-자식 구조를 파악하기 위함 
	queue<int> q;
	q.push(start);
	depth[start] = 0;
	visited[start] = 1;
	while (!q.empty()) {
		int temp = q.front();
		q.pop();
		for (int i = 0;i < graph[temp].size();i++) {
			int next = graph[temp][i];
			if (!visited[next]) {
				visited[next] = 1;
				parent[next][0] = temp;
				depth[next] = depth[temp] + 1;
				if (depth[next] > max_depth) max_depth = depth[next];
				q.push(next);
			}
		}
	}
}
int findCommonParent(int a, int b) {
	int a_d = depth[a];
	int b_d = depth[b];

	if (b_d > a_d) { // 항상 a_d >= b_d 이도록 
		int temp;
		temp = a; a = b; b = temp;
		a_d = depth[a]; b_d = depth[b];
	}
	// a, b 높이 맞추기 
	int gap = a_d - b_d; int d = 0;
	while (gap) {
		if (gap % 2 == 1) {
			a = parent[a][d];
		}
		d++;
		gap /= 2;
	}
	if (a == b) return a;
	//a와 b의 부모가 같도록 맞춰줌 
	// maxD부터 시작하는 이유 : 가장 "가까운" 공통 조상을 구해야 하므로, 
	// j가 0이랑 최대한 가까울 때가 답이 되어야함 
	for (int j = maxD - 1;j >= 0;j--) { 
		if (parent[a][j] != parent[b][j]) {
			a = parent[a][j]; b = parent[b][j];
		}
	}
	
	a = parent[a][0];
	return a;
}
int main() {
	sc("%d", &N);
	for (int i = 1;i < N;i++) {
		int a, b;
		sc("%d %d", &a, &b);
		graph[a].push_back(b);
		graph[b].push_back(a);
	}

	// 트리 만들기 
	BFS(1);

	// DP 값 채우기 
	for (int i = 0;i < maxD;i++) {
		for (int j = 1;j <= N;j++) {
			int k = parent[j][i];
			if (k != 0) parent[j][i + 1] = parent[k][i];
		}
	}

	sc("%d", &M);
	for (int i = 0;i < M;i++) {
		int a, b;
		sc("%d %d", &a, &b);
		// 공통조상 찾아 출력
		printf("%d\n", findCommonParent(a, b));
	}
	return 0;
}

결과

11437 LCA 1

11438 LCA 2