[백준/BOJ] 백준 2644번 : 촌수계산

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

2644번: 촌수계산

human_a에서 human_b로 bfs를 통해 도달할 때 지나온 간선의 수, 즉 depth를 구해 촌수를 계산한다. 

 

코드

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

int n, m;
vector<int> adj[101];
int discoverd[101];
int depth[101];

//human_a에서 bfs를 해 human_b에 도달했을때 depth를 구한다(지나온 간선의 수)
int Solve(int human_a, int human_b)
{
	discoverd[human_a] = 1;
	depth[human_a] = 0;

	queue<int> q;
	q.push(human_a);

	while (!q.empty())
	{
		int here = q.front();
		q.pop();

		//human_b에 도달했을때
		if (here == human_b)
			return depth[here];

		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i];

			//there가 발견되지 않은 노드일때
			if (discoverd[there] == 0)
			{
				discoverd[there] = 1;
				depth[there] = depth[here] + 1;

				q.push(there);
			}
		}
	}

	//human_a에서 human_b에 도달하지 못할때
	return -1;
}

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

	int human_a, human_b;
	int x, y;

	memset(discoverd, 0, sizeof(discoverd));

	cin >> n;
	cin >> human_a >> human_b;
	cin >> m;

	for (int i = 0; i < m; i++)
	{
		cin >> x >> y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}

	cout << Solve(human_a, human_b);

	return 0;
}