BOJ 백준 2644 촌수계산

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

<촌수계산>

 말 그대로 촌수 계산을 해 주는 문제이다.

입력값으로는 

1. 사람의 수

2. 촌수를 계산하려는 두 사람

3. 부모-자식 관계의 수 

4. 부모-자식 관계

이렇게 들어온다.

문제에서 원하는 것은 2번에 입력된 두 사람의 촌수를 출력해주는 것이다.

촌수를 계산하려는 두 사람의 공통되면서 최소인 부모노드를 찾고 찾아낸 부모노드로부터

촌수를 계산해주면 되는, 어렵지 않은 문제이다.

vector을 이용해서 두 사람의 부모노드들을 찾아 저장해주고, 비교해주면서 최소 부모 노드를 찾아내는

형태로 풀었으나, 사실 추가 배열 없이 parent[]라는 배열 하나로 문제 풀이가 가능하다.

#include <iostream>
#include <vector>
#define SIZE 101

using namespace std;

int		parent[SIZE];
int		n, m;
int		p1, p2;
int		iNum = 0;

void getParent(int u, vector<int> &v)
{
	v.push_back(u);
	if (u == parent[u]) return;
	getParent(parent[u], v);
}

int CompareParent(vector<int> &v1, vector<int> &v2)
{
	for (int i : v1)
	{
		for (int j : v2)
		{
			if (i == j) {
				return i;
			}
		}
	}
	return -1;
}

void solution(int u, int root)
{
	if (u == root) return;
	iNum++;
	solution(parent[u], root);
}

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

	cin >> n;
	cin >> p1 >> p2;
	cin >> m;

	for (int i = 1; i <= n; i++)
	{
		parent[i] = i;
	}
	
	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		parent[b] = a;
	}

	vector<int> vp1, vp2;
	getParent(p1, vp1);
	getParent(p2, vp2);

	int root;
	root = CompareParent(vp1, vp2);

	if (root == -1) cout << "-1" << '\n';
	else {
		solution(p1, root);
		solution(p2, root);

		cout << iNum << '\n';
	}

	return 0;
}