Baekjoon 11437 LCA

Link https://www.acmicpc.net/problem/11437

소스결과 7400 KB / 816 ms

언어 C++ 17

출처 Baekjoon

분류 LCA

 

설명

1을 루트로 하는 트리가 주어질 때 두 정점의 가장 가까운 공통 조상의 번호를 출력한다.

 

LCA를 처음 공부할 때 개념을 잡기 좋은 문제라고 한다.

다른 블로그를 돌아다니면서 개념을 익힐 때 왜 깊이를 DFS로 설정해 주는지 의문을 가졌었다.

예제를 직접 노트로 옮겨보니 바로바로 이어져서 입력과 동시에 깊이와 부모를 설정해 줬는데 제출을 하니 바로 시간초과에 걸렸었다.

TC로 들어오는건 꼭 1이 있는 트리에 이어져서 들어오는게 아니라 나눠져 들어오기 때문에 깊이와 부모 설정에 문제가 생겨 높이를 맞추는 과정에서 무한루프에 빠지게 됬었다.

 

원인을 알고나니 왜 블로그에서 DFS를 이용해서 깊이를 설정해 주는지 이해가 갔다.

 

vector를 이용해서 인접행렬을 구현하고, 깊이와 부모를 저장할 변수를 따로 지정해 DFS를 통해 부모와 깊이를 설정.

공통 조상을 찾을 두 노드의 높이를 낮은 쪽으로 맞춘 후, 두 노드가 같아질 때 까지 부모노드를 타고 올라방식으로 구현했다.

 

알고리즘

1. 노드의 개수와 간선 정보를 입력 받는다.

 1-1. 간선은 양방향 이기에 vector에 서로 입력해한다.

2. 1을 기점으로 DFS를 진행한다.

 2-1. 양방향이기 때문에 방문 체크를 진행할 변수를 전역변수로 선언한다.

 2-2. 연결된 정점 중에서 방문하지 않은 정점을 찾는다.

 2-3. 방문되지 않은 정점의 부모를 현재 정점으로 설정하고, 높이를 현재 정점의 높이 + 1로 설정한다.

 2-4. 방문하지 않은 정점을 기준으로 재귀 호출한다.

3. 탐색할 회수 m을 입력 받는다.

4. 두 정점을 입력 받는다.

5. 두 정점의 높이를 맞춘다.

 5-1. 두 정점 중 높이가 낮은 쪽으로 정점을 조절한다.

6. 두 정점이 같은 정점이 될 때 까지 바로 위 부모를 타고 올라가고 다른 경우 부모 정점이 현재 정점이 된다.

7. 각각의 경우를 출력 후 줄바꿈 한다.

 

소스코드

#include <iostream>
#include <vector>
#include <string.h>

using namespace std;

const int MAX = 50000;

vector<vector<int>> vertex;

int parent[MAX] = { };
int level[MAX] = { };
bool check[MAX];


void balancing(int& node1, int& node2) {

	while (level[node1] > level[node2])
		node1 = parent[node1];
	

	while (level[node1] < level[node2]) 
		node2 = parent[node2];
	
}

void setParNLevel(int node) {

	check[node] = true;

	int edgeCount = vertex[node].size();
	for (int i = 0; i < edgeCount; i++) {
		int vert = vertex[node][i];
		if (!check[vert]) {
			parent[vert] = node;
			level[vert] = level[node] + 1;
			setParNLevel(vert);
		}
	}
}

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

	int n, m;
	cin >> n;

	vertex.resize(n);

	for (int i = 0; i < n - 1; i++) {
		int to, des;

		cin >> to >> des;

		vertex[to - 1].push_back(des - 1);
		vertex[des - 1].push_back(to - 1);
	}

	setParNLevel(0);

	cin >> m;

	for (int i = 0; i < m; i++) {
		int node1, node2;

		cin >> node1 >> node2;

		node1--; node2--;

		balancing(node1, node2);

		while (node1 != node2) {
			node1 = parent[node1];
			node2 = parent[node2];
		}

		cout << node1 + 1 << '\n';
	}

	return 0;
}