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

www.acmicpc.net/problem/2644

2644번: 촌수계산

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

int target1;
int target2;
int cnt;
vector<int> info[100];
bool checkArr[100];
bool bIsSuc = false;
int resultCnt = 9999;


void D(int _n)
{
	if (_n == target2)
	{
		bIsSuc = true;
		if (cnt < resultCnt)
			resultCnt = cnt;		
	}
	else
	{
		for (int i = 0; i < info[_n].size(); i++)
		{
			int nextTarget = info[_n][i];
			if (checkArr[nextTarget] == false)
			{
				checkArr[nextTarget] = true;
				cnt++;
				D(nextTarget);
				cnt--;
				checkArr[nextTarget] = false;
			}
		}
	}
}
int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int totalPeople;
	cin >> totalPeople;

	cin >> target1 >> target2;


	int n2;
	cin >> n2;
	int input1;
	int input2;

	for (int i = 0; i < n2; i++)
	{
		cin >> input1 >> input2;

		info[input1].push_back(input2);
		info[input2].push_back(input1);
	}


	checkArr[target1] = true;
	D(target1);

	if(bIsSuc)
		cout << resultCnt << endl;
	else
	{
		cout << -1 << endl;
	}
	return 0;
}