[백준] 3584번 가장 가까운 공통 조상

기본적인 트리 문제로 해당 노드의 부모 값만 잘 설정해준다면 어려움없이 풀 수 있다. 구조체 배열을 사용하여 풀었지만 풀고 나니 그냥 int형 배열을 사용하여 해당 index의 값을 부모로 설정해도 풀 수 있을 것 같다.

 

 

구조체 node에 부모를 가르키는 parent와 해당 node의 숫자 num을 저장했다.

 

 

크기가 10005인 node형 벡터를 선언하고 N-1개의 node 값을 입력 받으며 벡터에 값을 넣어준다.

 

 

공통 조상을 구할 두 개의 노드를 입력 받고 해당 노드의 부모들을 큐에 저장한다.

 

 

두 노드의 큐의 크기가 다를 경우 같게 해준 뒤 하나씩 빼면서 값이 같은지 비교를 한다. 크기를 같게 해주는 이유는 예시로 { 1, 2, 3 } 과 { 10, 9, 2, 3 } 인 경우 크기가 더 큰 오른쪽의 10은 절대로 답이 될 수 없고 비교를 할 때 공통 조상인 '2'로 부터 거리가 각각 1, 2로 다르기 때문에 비교할 때 서로 안맞게 된다.

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

struct node {
	node* parent;
	int num;
};


int T;

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

	cin >> T;

	while (T--) {
		int N;
		cin >> N;

		vector<node> nodes(10005);

		for (int i = 0; i < N - 1; i++) {
			int parent, child;
			cin >> parent >> child;
			
			nodes[child].num = child;
			nodes[child].parent = &nodes[parent];
			nodes[parent].num = parent;
		}

		// 마지막 줄의 두 노드
		int num1, num2;
		cin >> num1 >> num2;

		// 두 노드의 부모들을 저장할 큐
		queue<int> pnum1, pnum2;

		// 첫 번째 노드와 부모들 저장
		node cur = nodes[num1];
		pnum1.push(cur.num);
		while (cur.parent != NULL) {
			pnum1.push(cur.parent->num);
			cur = *cur.parent;
		}

		// 두 번째 노드와 부모들 저장
		cur = nodes[num2];
		pnum2.push(cur.num);
		while (cur.parent != NULL) {
			pnum2.push(cur.parent->num);
			cur = *cur.parent;
		}

		// 만약 두 노드의 부모 수가 다를 경우 부모 수를 같게 해준다.
		// 예를 들어, { 15, 6, 4, 8} 과 { 3, 16, 10, 4, 8} 일 경우
		// 한 칸씩 밀려서 안 맞기 때문
		if (pnum1.size() > pnum2.size()) {
			int n = pnum1.size() - pnum2.size();
			for (int i = 0; i < n; i++) {
				pnum1.pop();
			}
		}
		else if (pnum1.size() < pnum2.size()) {
			int n = pnum2.size() - pnum1.size();
			for (int i = 0; i < n; i++) {
				pnum2.pop();
			}
		}

		// 맨 앞 하나씩 빼면서 비교
		while (pnum1.front() != pnum2.front()) {
			pnum1.pop();
			pnum2.pop();
		}

		cout << pnum1.front() << '\n';
	}

	

	return 0;
}