[BOJ] 11437 LCA

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

Note

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

LCA를 처음 공부할 때 개념을 잡기 좋은 문제라고 한다.
다른 블로그를 돌아다니면서 개념을 익힐 때 왜 깊이를 DFS로 설정해 주는지 의문을 가졌었다.
예제를 직접 노트로 옮겨보니 바로바로 이어져서 입력과 동시에 깊이와 부모를 설정해 줬는데 제출을 하니 바로 시간초과에 걸렸었다.
TC로 들어오는건 꼭 1이 있는 트리에 이어져서 들어오는게 아니라 나눠져 들어오기 때문에 깊이와 부모 설정에 문제가 생겨 높이를 맞추는 과정에서 무한루프에 빠지게 됬었다.

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

vector를 이용해서 인접행렬을 구현하고, 깊이와 부모를 저장할 변수를 따로 지정해 DFS를 통해 부모와 깊이를 설정.
공통 조상을 찾을 두 노드의 높이를 낮은 쪽으로 맞춘 후, 두 노드가 같아질 때 까지 부모노드를 타고 올라방식으로 구현했다.

알고리즘

1. 노드의 개수와 간선 정보를 입력 받는다.
   1. 간선은 양방향 이기에 vector에 서로 입력해한다.
2. 1을 기점으로 DFS를 진행한다.
   1. 양방향이기 때문에 방문 체크를 진행할 변수를 전역변수로 선언한다.
   2. 연결된 정점 중에서 방문하지 않은 정점을 찾는다.
   3. 방문되지 않은 정점의 부모를 현재 정점으로 설정하고, 높이를 현재 정점의 높이 + 1로 설정한다.
   4. 방문하지 않은 정점을 기준으로 재귀 호출한다.
3. 탐색할 회수 m을 입력 받는다.
4. 두 정점을 입력 받는다.
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;
}

2019-04-22 16:46:02에 Tistory에서 작성되었습니다.