[BOJ] #2644 _ 촌수계산

[촌수계산] https://www.acmicpc.net/problem/2644

2644번: 촌수계산

부모가 한명 뿐이기 때문에 부모만 저장하여 쉽게 풀 수 있다.

 

부모배열에 부모를 다 저장해두고,

상위로 올라가면서 공통의 부모를 찾아 촌수를 계산할 수 있다. (부모와 자식의 촌수는 1)

 

예를 들어, 아래와 같은 가족 관계가 있을 때, 4와 3의 촌수를 계산해보자.

 

4와 3의 공통 부모는 1이다.

따라서, 4 ~ 1의 촌수와 3 ~ 1의 촌수를 더하면 4와 3의 촌수가 된다.

 

이와 같은 방법으로 공통 부모를 찾아 촌수를 계산하면 된다.

 

[ 소스 코드 ]

 

#include <cstdio>
#include <vector>
#include <algorithm>
#define MAX 101

using namespace std;
int n, num_1, num_2, r_num;
int p[MAX];

int solve();
int main() {
	int a, b;

	scanf("%d", &n);
	scanf("%d %d", &num_1, &num_2);

	scanf("%d", &r_num);
	for (int i = 0; i < r_num; i++) {
		scanf("%d %d", &a, &b);
		p[b] = a;
	}

	printf("%d\n", solve());

	return 0;
}

int solve() {
	vector<int> tmp1, tmp2;
	tmp1.push_back(num_1);
	tmp2.push_back(num_2);

	while (1) {
		if (p[tmp1[tmp1.size() - 1]] == 0) break;
		tmp1.push_back(p[tmp1[tmp1.size() - 1]]);
	}
	while (1) {
		if (p[tmp2[tmp2.size() - 1]] == 0) break;
		tmp2.push_back(p[tmp2[tmp2.size() - 1]]);
	}

	for (int i = 0; i < tmp1.size(); i++) {
		for (int j = 0; j < tmp2.size(); j++) {
			if (tmp1[i] == tmp2[j]) return i + j;
		}
	}

	return -1;
}