백준 촌수계산

이 문제는 어떤 번호를 부여 받을 때 이 번호간 촌수가 몇촌인지 구하는 문제다.

 

BFS와 그래프를 이용해 해결했다.

 

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;

int dx[8] = { 1, 0, -1, 0,-1,-1,1,1 };
int dy[8] = { 0, 1, 0, -1,-1,1,-1,1 };
int cnt;
int n, m;
int dp[101][101];
bool visited[51][51];

int main() {
	cin >> n;
	int to, from;
	int x, y;
	cin >> to >> from;
	cin >> m;
	vector<vector<int>> graph(n + 1);

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

	dp[to][to] = 0;
	queue<int> q;
	q.push(to);
	while (!q.empty()) {
		int cur = q.front();
		q.pop();

		for (auto it : graph[cur]) {
			if (dp[to][it] > 0) {
				continue;
			}
			dp[to][it] = dp[to][cur] + 1;
			q.push(it);
		}
	}

	if (dp[to][from] == 0) {
		cout << -1 << '\n';
	}
	else {
		cout << dp[to][from] << '\n';
	}
	
	return 0;
}

 

촌수는 dp에 세팅해서 구했고 자기자신은 0촌으로 시작해 to로부터 연결되는 dp[to]로 부터 연결지점을 계속 증가시켜 구해주었다.