11437번: LCA

문제 설명

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

11437번: LCA

[문제]

 N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.

 두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.

 

[입력]

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

 

[출력]

 M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.

 

[예제 입력 1]

15
1 2
1 3
2 4
3 7
6 2
3 8
4 9
2 5
5 11
7 13
10 4
11 15
12 5
14 7
6
6 11
10 9
2 6
7 6
8 13
8 15

[예제 출력 1]

2
4
2
1
3
1

---

풀이

 문제에서 요구하는 알고리즘은 단순히 공통 조상 찾기이다. 게다가 문제에서 시간을 넉넉히 주기 때문에 두 노드에서 직접 비교를 통해 거슬러 올라가며 찾아도 큰 문제가 되지 않는다. 다만 문제에서 입력을 주는 정보가 단순히 노드 연결 관계기 때문에, 이들을 가지고 트리 구조를 필요에 맞게 정리할 필요가 있다.

 단순히 문제에서 주어진 정보는 트리의 루트 노드가 1번이라는 것 밖에 없기 때문에 1번 노드에서 시작해서 트리 구조를 정리해야 한다. 흔히 공통 조상 찾기에서 필요한 자료는 현 트리 노드의 부모 노드기 때문에, 정리를 통해 각 노드의 부모 노드가 무엇인지를 정리해야 한다.

 우선 1번 루트 노드에서 시작하여, 연결 관계를 저장한 자료구조에서 해당 노드에 연결된 노드들을 찾아 부모 노드를 저장한다. 이후 재귀 호출을 통해 연결된 노드 번호에서 시작해서 또 자식 노드에 대해 부모 노드를 찾는 과정을 반복한다. 이 때 앞서 말했듯이 단순 노드 연결관계 저장에서는 루트 노드를 제외하고 노드에 연결된 다른 노드 중 부모 노드가 있을 수 있기 때문에, 방문 확인 배열을 만들어 이를 확인한다.

 이렇게 트리 정리가 끝나면 이후 들어오는 두 노드에 대해 공통 조상 찾기를 진행하여 이를 반환하면 된다.

#include <iostream>
#include <vector>

using namespace std;

vector<int> connection[50001];//단순 노드 연결관계 저장
int parent[50001];//노드의 부모
int check[50001];//공통 조상 찾기
bool visited[50001];//노드 정리를 위한 방문 배열

int findMinCommonAncestor(int node1, int node2, int temp) {//최소 공통 조상 찾기
	int tempNode1 = node1, tempNode2 = node2;

	while (1) {
		if (tempNode1 != 0) {
			if (check[tempNode1] == temp)
				return tempNode1;

			check[tempNode1] = temp;
			tempNode1 = parent[tempNode1];
		}

		if (tempNode2 != 0) {
			if (check[tempNode2] == temp)
				return tempNode2;

			check[tempNode2] = temp;
			tempNode2 = parent[tempNode2];
		}
	}

	return 1;
}

void treeSort(int node) {//부모 노드 정리
	for (int i = 0; i < connection[node].size(); i++) {
		if (!visited[connection[node][i]]) {
			visited[connection[node][i]] = true;
			parent[connection[node][i]] = node;
			treeSort(connection[node][i]);
		}
	}
}

int main() {
	int N, M;
	int node1, node2;
	vector<int> result;

	parent[1] = 0;
	cin >> N;

	for (int i = 1; i < N; i++) {//연결 관계 저장
		cin >> node1 >> node2;
		connection[node1].push_back(node2);
		connection[node2].push_back(node1);
	}

	visited[1] = true;
	treeSort(1);//트리 정리

	cin >> M;

	for (int i = 0; i < M; i++) {
		cin >> node1 >> node2;
		result.push_back(findMinCommonAncestor(node1, node2, i + 1));
	}

	
	for (int i = 0; i < M; i++) {
		cout << result[i] << "\n";
	}

	return 0;
}

---

결과