[백준,c++] 3584번 - 가장 가까운 공통 조상

문제

3584번: 가장 가까운 공통 조상

 

코드

#include <iostream>
#include <vector>
#include <memory.h>
using namespace std;


bool visited[10001];

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

	int T; cin >> T;
	while (T--) {
		int N; cin >> N;
		vector<int>graph(N + 1);

		for (int i = 1; i <= N - 1; i++) {
			int a, b; cin >> a >> b;
			graph[b] = a;
		}
		int a, b; cin >> a >> b;
		visited[a] = true;
		while (a != graph[a]) {
			visited[a] = true;
			a = graph[a];
		}

		while (true) {

			if (visited[b] == true) {
				cout << b << '\n';
				break;
			}
			b = graph[b];

		}
		memset(visited, 0, sizeof(visited));
	}
}

 

풀이

위와 같은 트리가 주어졌을 때 두 노드의 가장 가까운 공통 조상 노드를 찾는 문제입니다. 

1. 먼저 입력받은 노드들마다 부모 노드를 기억해줍니다.
2. 두 노드 중 한 노드를 잡아서 해당 노드와 부모 노드를 전부 방문처리합니다.
3. 남은 한 노드를 잡아서 해당 노드의 부모 노드를 전부 방문할 때 방문 처리가 이미 된 노드가 있으면 해당 노드가 가장 가까운 공통 조상 노드가 됩니다.