[백준 2644] 촌수계산

풀이

핵심은 촌수 관계를 어떻게 코드로 풀어낼 것인지다.

 

이 문제는 N의 범위가 100밖에 되지 않기 때문에 인접 행렬 or 인접 리스트 중 하나를 선택해서 구현하면 된다.

 

인접 리스트로 구현한다고 할 때,

부모 자식 간의 관계를 나타내는 번호가 a, b로 주어지게 된다면, 서로 양방향으로 넣어줘야 한다는 것만 주의하면 쉽게 해결할 수 있다.

 

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

// 어떻게 촌수를 표현할 지?
vector<int> v[101];
bool vis[101];
int n, m, x, y;

int bfs()
{
	queue<pair<int, int>> q;
	q.push({ x,0 });
	vis[x] = true;
	while (!q.empty())
	{
		int now = q.front().first;
		int cost = q.front().second;
		q.pop();

		if (now == y) return cost;

		for (int i = 0; i < v[now].size(); ++i)
		{
			int next = v[now][i];
			if (!vis[next])
			{
				vis[next] = true;
				q.push({ next,cost + 1 });
			}
		}
	}

	// 두 사람이 친척 관계가 없다.
	return -1;
}

int main()
{
	cin >> n >> x >> y >> m;
	for (int i = 0; i < m; ++i)
	{
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}

	cout << bfs() << '\n';
	return 0;
}