백준 11438번 LCA2

< 백준 11438번 LCA2 - 마포 코딩박 >

사용한 알고리즘: LCA (최소공통조상)


 LCA 를 구현할 줄 알아야 풀 수 있는 문제였습니다.
강산님 블로그 https://blog.naver.com/kks227/220820773477 를 많이 참고하여 풀었습니다. LCA 에 대한 자세한 설명이 있으니 참고하시면 좋을 것 같습니다.

풀이 방법은 다음과 같습니다.
( 사실 LCA 구현법입니다. )

(1) (코드 6~7)
 'parent[i][k] : i의 2^k 번째 조상' 라고 설정해줍니다.

(2) (코드 13~22, 36~37)
 depth[0]=0 으로 설정하고 각 노드들의 depth를 정하며 트리를 구성합니다.
 이때 parent[i][0] 는 바로 위 부모이므로 이를 설정해줍니다.

(3) (코드 39~45)
 parent[i][0] 를 설정 해 둔 것을 바탕으로 2^k 번째 부모들을 구해줍니다.

(4) (코드 47~79)
 입력으로 두 노드 a, b 를 받으면, 높이를 맞춰 준 후
 (이때 a==b가 되면 그 노드가 공통 조상입니다.),
 최대 조상 (2^17) 부터 둘의 조상을 비교하면서 내려오며, 둘의 2^k 번째 조상이 다른 경우 해당 위치로 a, b 를 각각 재조정해줍니다.
 과정이 끝난 후 a, b 는 같은 부모 밑에 있게 됩니다. 이는 찾고자 하는 최소공통조상입니다.

 LCA 구현의 대표적인 문제였습니다.

	#include <bits/stdc++.h>
	using namespace std;
	// 노드 수 해봤자 10^5 < 2^17 이므로 어떤점이든 2^17번째 부모까지만 보면됨
	const int MAX = 18;
	int N, M;
	// parents[i][k] : i의 2^k 번째 부모
	int parents[100000][MAX];
	// 노드의 깊이 ( 루트는 깊이 0 )
	int depth[100000];
	// 인접 리스트
	vector<int> adj[100000];
	// DFS 로 트리 제작, 각 노드들의 2^0 부모 와 깊이 저장
	void MakeTreeDFS(int curr){
	for(int next: adj[curr]){
	if(depth[next]==-1){
	parents[next][0] = curr;
	depth[next] = depth[curr]+1;
	MakeTreeDFS(next);
	}
	}
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N;
	for (int i = 0; i < N-1; ++i){
	int a, b;
	cin >> a >> b;
	a--;
	b--;
	adj[a].push_back(b);
	adj[b].push_back(a);
	}
	// parents 값을 -1로 초기화 하고 시작
	memset(parents,-1,sizeof(parents));
	fill(depth,depth+N, -1);
	// root 의 깊이는 0
	depth[0] = 0;
	// 트리 만들어~
	MakeTreeDFS(0);
	// i 의 2^j 번째 부모 k가 있으면, i의 2^j * 2 번째 부모는 k의 2^j번째 부모
	for (int j = 0; j < MAX-1; ++j){
	for (int i = 1; i < N; ++i){
	int k = parents[i][j];
	if(k!=-1) parents[i][j+1] = parents[k][j];
	}
	}
	cin >> M;
	for (int i = 0; i < M; ++i){
	int a, b;
	cin >> a >> b;
	a--;
	b--;
	// depth[a] >= depth[b] 로 생각하기 위해 조정
	if(depth[a] < depth[b]) swap(a,b);
	int diff = depth[a] - depth[b];
	// a 와 b 를 같은 높이로 맞춰주기
	int j = 0;
	while(diff){
	if(diff%2) {
	a = parents[a][j];
	}
	j++;
	diff/=2;
	}
	// a==b 이면 a=b 가 공통조상이겠죠.
	if(a!=b){
	// 2^17, 2^16, ... 2, 1 번째 부모를 비교
	// 가장 중요한 스킬!!!!!!!!!!!1
	for (int j = MAX-1; j>=0; j--){
	// 2^j번째 조상이 다른게 나오면 a, b 를 각각의 2^j번째 조상으로 위치변경
	if(parents[a][j]!=parents[b][j]){
	a = parents[a][j];
	b = parents[b][j];
	}
	}
	// 위 과정이 끝나면 최종 a, b 는 같은 부모 아래 있다.
	a = parents[a][0];
	}
	cout << a+1 << '\n';
	}
	return 0;
	}

view raw BOJ 11438.cpp hosted with ❤ by GitHub