mojo's Blog

[백준 11438] LCA 2 본문

백준/Graph

[백준 11438] LCA 2

_mojo_ 2021. 7. 20. 15:45

문제 링크 => 11438번: LCA 2 (acmicpc.net)

 

11438번: LCA 2

첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정

www.acmicpc.net


트리를 이용한 최소 공통 조상을 찾는 문제이다.

 

이문제는 LCA 11437번: LCA (acmicpc.net) 이 문제와 다르게 N 값이 100,000으로 주어졌다.

 

따라서 1차원 배열로 해결할 경우 시간 초과가 발생한다.

 

따라서 부모배열을 1차원 배열이 아닌 2차원 배열로 변경하여 parent[x][y] 로 수정해준다.

 

parent[x][y] => x의 노드에서 2^y 위에 존재하는 부모의 노드이다.

 

예를 들어서 노드가 다음과 같이 연결된걸로 가정한다. 

 

ex) 1 => 2 => 4 => 8 => 16 => ... => 2^n 일 때,

parent[16][0] = 8 <= 노드 16의 2^0 위에 있는 부모 노드는 8

parent[16][1] = 4 <= 노드 16의 2^1 위에 있는 부모 노드는 4 ( 노드 8의 2^0 위에 있는 부모 노드 )

parent[16][2] = 2 <= 노드 16의 2^2 위에 있는 부모 노드 ( 노드 8의 2^1 위에 있는 부모 노드 = 노드 4의 2^0 위에 있는 부모 노드 )

... 

이 규칙을 일반화한다면 다음과 같은 식을 얻는다.

parent[x][y] = parent[parent[x][y-1]][y-1]

그렇다면 2차원 배열 parent를 통해 어떻게 최소 공통 조상을 찾는지에 대해서 다음 방법을 살펴보도록 한다.

 

  1. depth[x] > depth[y] 가 되도록 하는 노드 x, y를 설정한다. (LCA와 동일)
  2. depth[x] == depth[y] 가 되도록 하기 위해 depth[y] - depth[x] >= 2^i 즉, 차이가 발생하는 경우 y = parent[y][i] 를 해줘서 2^i 번째 노드로 이동시켜주는 작업을 한다. ( i = 20, 19, ... , 0 역순으로 진행해야 함 )
  3. 이때 x == y 인 경우 먼저 반환한다.
  4. x != y 인 경우 depth[x] == depth[y] 임을 이용해서 parent[x][i] != parent[y][i] 일 때, x = parent[x][i], y = parent[y][i] 를 해줌으로써 x, y의 2^0 위에 있는 부모 노드가 동일해질때까지 진행하고 parent[x][0] 을 반환한다.

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'
#define MOD 1000000009
#define ll long long

using namespace std;

vector<int> v[100001];
bool visited[100001];
int parent[100001][21]; 
int depth[100001]; 
int n;

void compose_Parent(int start) {
	queue<int> q;
	q.push(start);
	visited[start] = true;

	while (!q.empty()) {
		int mom = q.front();
		q.pop();
		for (int i = 0; i < v[mom].size(); i++) {
			int child = v[mom][i];
			if (!visited[child]) {
				visited[child] = true;
				parent[child][0] = mom;
				depth[child] = depth[mom] + 1;
				q.push(child);
			}
		}
	}

	for (int i = 1; i < 21; i++) {
		for (int j = 1; j <= n; j++) {
			parent[j][i] = parent[parent[j][i - 1]][i - 1];
		}
	}
}

int LCA(int x, int y) {
	if (depth[x] > depth[y]) {
		swap(x, y);
	}
	for (int i = 20; i >= 0; i--) {
		if (depth[y] - depth[x] >= pow(2, i)) {
			y = parent[y][i];
		}
	}
	if (x == y) return x;
	for (int i = 20; i >= 0; i--) {
		if (parent[x][i] != parent[y][i]) {
			x = parent[x][i];
			y = parent[y][i];
		}
	}
	return parent[x][0];
}


int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}

	compose_Parent(1);

	int m;
	cin >> m;
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		cout << LCA(x, y) << endl;
	}

	return 0;
}

'백준 > Graph' 카테고리의 다른 글

[백준 6543] 그래프의 싱크  (0) 2021.07.26
[백준 1761] 정점들의 거리  (0) 2021.07.20
[백준 11437] LCA  (0) 2021.07.20
[백준 19535] ㄷㄷㄷㅈ  (0) 2021.07.17
[백준 13911] 집 구하기  (0) 2021.07.06
Comments