[백준2644] 촌수계산

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

입력

사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.

각 사람의 부모는 최대 한 명만 주어진다.

출력

입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력한다. 어떤 경우에는 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때가 있다. 이때에는 -1을 출력해야 한다.

풀이

start에서 end까지의 노드수를 계산하는 문제이다.
양방향으로 받은 후 start에서 bfs 시작
count 방식으로 풀려했지만 실패하고
visited를 int로 준 다음 visitied에 카운트하고 0은 방문하지 않는 식으로 풀이 함.
end 번째 노드일 시 함수 종료, 만약 함수 종료 안하고 bfs 종료면 -1 출력

코드

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

int n;
int cnt=0;
vector<vector<int>>arr;
vector<int>visitied;
int start, endd, m;
bool flag = true;
void bfs(int i)
{

	queue<int>myque;
	myque.push(i);
	visitied[i] += 1;
	while (!myque.empty())
	{
		int now = myque.front();
		myque.pop();
		for (auto i : arr[now])
		{
		
			if (visitied[i] == 0)
			{
				myque.push(i);
				visitied[i]=visitied[now]+1;
				if (i == endd)
				{
					return;
				}
			}
		}
	}
	flag =false;

	cout << "-1" << "\n";
	return;

}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n>>start>> endd >>m;
	visitied.resize(n + 1,0);
	arr.resize(n + 1);
	for (int i = 1; i <= m; i++)
	{
		int a, b;
		cin >> a >> b;
		arr[a].push_back(b);
		arr[b].push_back(a);
	}
	bfs(start);

	if (flag)
	{
		cout << visitied[endd]-1<<"\n";
	}

}