BOJ - 3584번, 가장 가까운 공통 조상 [LCA]

이번에 풀이한 문제는 3584번 LCA(Lowest Common Ancestor), 최소 공통 조상 문제입니다.

 

문제 제목에서 알 수 있듯이, 트리 정보를 입력받은 후에 두 개의 노드의 최소 공통 조상을 찾으면 되는 문제입니다.

15와 11의 최소 공통 조상은 4이다.

최소 공통 조상은 위 그림과 같이 부모 노드로 타고 올라갈 때, 가장 높이가 낮으면서, 두 개의 노드의 공통 조상인 노드입니다.

 

이러한 유형을 풀어봤던 것 같은데, 각 노드의 부모 노드 정보를 저장한 뒤에 이를 활용해야 한다는 부분까지는 생각이 났는데, 정확한 알고리즘이 생각나지 않아 다른 분들의 풀이를 참고했습니다.

 

더 효율적인 방법이 있겠지만, 일단 이 문제에 적용할 수 있는 가장 쉬운 풀이는 하나의 노드가 먼저 부모를 거슬러 올라가며, 방문 처리하며 탐색한 뒤에 두 번째 노드가 탐색해 가며 처음으로 첫 번째 노드에 의해 방문 처리된 노드를 찾는 방식으로 최소 공통 조상을 찾는 방식이었습니다.

---

문제

루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다.

• 두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다.

예제 입력의 첫 번째 트리

예를 들어  15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그중 깊이가 가장 깊은(15와 11에 가장 가까운) 노드는 4 이므로 가장 가까운 공통 조상은 4가 됩니다.

루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성하세요

 

입력

첫 줄에 테스트 케이스의 개수 T가 주어집니다.

각 테스트 케이스마다, 첫째 줄에 트리를 구성하는 노드의 수 N이 주어집니다. (2 ≤ N ≤ 10,000)

그리고 그 다음 N-1개의 줄에 트리를 구성하는 간선 정보가 주어집니다. 한 간선 당 한 줄에 두 개의 숫자 A B 가 순서대로 주어지는데, 이는 A가 B의 부모라는 뜻입니다. (당연히 정점이 N개인 트리는 항상 N-1개의 간선으로 이루어집니다!) A와 B는 1 이상 N 이하의 정수로 이름 붙여집니다.

테스트 케이스의 마지막 줄에 가장 가까운 공통 조상을 구할 두 노드가 주어집니다.

 

출력

각 테스트 케이스 별로, 첫 줄에 입력에서 주어진 두 노드의 가장 가까운 공통 조상을 출력합니다.

 

예제 입력 1

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

예제 출력 1

4
3

---

풀이 과정 정리

우선 앞서 정리한대로 입력으로 받은 간선 정보를 이용해서, 각 노드의 부모 노드 정보를 저장했습니다.

setParent method를 이용해 부모 정보를 저장

a가 b의 부모임을 p 배열에 기록

다음으로 하나의 노드가 먼저 부모를 거슬러 올라가며, 방문 처리하며 탐색한 뒤에 두 번째 노드가 탐색해 가며처음으로 첫 번째 노드에 의해 방문 처리된 노드를 찾는 방식으로 최소 공통 조상을 찾는 방식을 코드로 구현하면 다음과 같습니다.

방문 처리는 visited 배열을 선언해서 사용

이렇게 LCA를 해결하는 가장 간단한 방식으로 문제를 풀어봤습니다.

---

제출한 코드 (C++)

#include <iostream>

#define MAX 10001
#define endl '\n'

using namespace std;

int p[MAX];
int n;

void init() {
	//초기에는 자기 자신을 부모로 가리킨다. (아무것도 연결 x)
	for (int i = 1; i <= n; i++) {
		p[i] = i;
	}
}

//a가 b의 부모이다.
void setParent(int a, int b) {
	p[b] = a;
	return;
}

int findSameParent(int a, int b) {
	int parentA = a;
	int parentB = b;

	bool visited[MAX] = { false, };
	visited[parentA] = true;
	
	while (1) {
		if (parentA == p[parentA])
			break;

		parentA = p[parentA];
		visited[parentA] = true;
	}

	while (1) {
		if (visited[parentB])
			break;

		parentB = p[parentB];
	}

	return parentB;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int t;

	cin >> t;

	while (t--) {
		cin >> n;
		init();

		for (int i = 0; i < n - 1; i++) {
			int a, b;
			cin >> a >> b;

			setParent(a, b);
		}

		int a, b; //공통 조상을 구하고 싶은 두 개의 노드
		cin >> a >> b;

		cout << findSameParent(a, b) << endl;
	}

	return 0;
}

---

참고

https://cocoon1787.tistory.com/506

[C/C++] 백준 3584번 - 가장 가까운 공통 조상 (LCA)