[C++]백준 2644번: 촌수계산

문제

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

2644번: 촌수계산

문제이해

• 가족 구성원 수와 관계를 알고싶은 두 가족 구성원의 번호 입력한다.
• 그 다음으로 가족구성원 사이의 관계의 수를 입력하고 관계의 수만큼 가족 구성원들 간의 관계를 입력한다.
• 출력으로 두 가족 구성원이 몇촌인지를 나타낸다. 만약 두 가족 구성원이 서로 관계가 없을 경우 -1을 출력한다.

어떤 자식에 대해서 부모는 반드시 한명이여야 하며 어떤 부모에 대해서 자식의 수는 제한이 없다. graph를 이용해 가족 구성원의 관계를 구현하고 관계를 알고싶은 두 가족 구성원 사이의 관계를 알아내는 함수만 만들어주면 된다.

 

문제해결

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

struct member
{
	int N;
	member* up;
	vector<member*> down;
	member(int n) {
		N = n;
		up = NULL;
	}
};

vector<member*> family;

void setRelation(int h1, int h2) {
	family[h1 - 1]->down.push_back(family[h2 - 1]);
	family[h2 - 1]->up = family[h1 - 1];
}

void searchDown(member* curMem, member* target, int count, int& check) {
	count++;
	for (int i{ 1 }; i <= curMem->down.size(); i++) {
		if (target == curMem->down[i - 1]) {
			cout << count;
			check = 1;
			return;
		}
		else {
			searchDown(curMem->down[i - 1], target, count, check);
		}
	}
	return;
}

void getRelation(int h1, int h2, int count) {
	int check{};
	member* curMem = family[h1 - 1];
	int count1{ 0 };
	while (curMem->up != NULL) {
		count1++;
		curMem = curMem->up;
		if (curMem == family[h2 - 1]) {
			cout << count1;
			return;
		}
		searchDown(curMem, family[h2 - 1], count1, check);
		if (check == 1) {
			return;
		}
	}
	curMem = family[h2 - 1];
	count1 = 0;
	while (curMem->up != NULL) {
		count1++;
		curMem = curMem->up;
		if (curMem == family[h1 - 1]) {
			cout << count1;
			return;
		}
		searchDown(curMem, family[h1 - 1], count1, check);
		if (check == 1) {
			return;
		}
	}
	cout << "-1";
	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int N, M;
	cin >> N;
	for (int i{ 1 }; i <= N; i++) {
		member* newMem = new member(i);
		family.push_back(newMem);
	}
	int pl1, pl2;
	int re1, re2;
	cin >> pl1 >> pl2;
	cin >> M;
	for (int i{ 1 }; i <= M; i++) {
		cin >> re1 >> re2;
		setRelation(re1, re2);
	}
	getRelation(pl1, pl2, 0);
}

struct member

가족 구성원의 번호와 부모, 자식들의 정보를 저장할 수 있는 struct를 통해 graph를 만들었다. 부모는 반드시 한명이기 때문에 member* up으로 했지만 자식의 수는 여러명이 될 수 있기 때문에 vector<member*> down으로 벡터에 저장하기로 하였다.

void setRelation

m을 입력한 후 주어지는 가족 관계들을 설정하기 위한 함수로 자식의 부모는 h1, 부모의 자식은 h2다.

void searchDown

특정 구성원의 자손들을 조사하기위해 재귀함수 searchDown를 이용했다. count는 몇촌까지 왔는지를 알기 위해 넣었고 check는 재귀함수를 사용했을 때 getRelation함수에서 자식중에 찾고자 하는 구성원이 있었는지 확인하기 위해 넣었다.

특정 부모의 자식들중 찾고자 하는 가족 구성원이 있는지 확인한 후 없을 경우 그 자식들의 자식들중에 가족 구성원이 있는지 확인하는 방식으로 재귀함수를 만들었다.

void getRelation

h1과 h2 사이의 관계를 알아내기 위한 함수로 현재 조사 대상인 curMem을 계속 위로 올리면서 해당 curMem에 대해 searchDown을 사용하였다.

문제후기

촌을 어떻게 구해야 할지 잘 몰랐지만 방법을 찾은 이후로는 쉽게 했던 것 같다.