백준 2644 촌수계산 C++

주어진 두 사람의 촌수를 계산하는 문제.

dfs로 주어진 두 노드 간의 거리를 구하면 된다.

dfs의 매개변수에 노드간의 거리를 계산할 수 있는 chon이라는 변수를 만들어 주었다.

dfs가 실행되어 깊이가 깊어질 때마다 chon의 값을 1씩 증가시키면 촌수 계산을 쉽게 할 수 있다.

주어진 두 노드 중 하나를 기점으로 다른 한 점까지의 거리를 구하면 되기 때문에, 먼저 주어진 노드의 번호를 다음에 탐색할 노드의 번호로 바꾸면서 탐색하도록 하였다.

전형적인 dfs문제이므로 dfs의 형태를 안다면 쉽게 풀 수 있는 문제이다.

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

int n, m, a, b, ans;
bool visited[101] = { false, };
vector<int> v[101];

void dfs(int a, int b, int chon) {
	visited[a] = true;
	if (a == b) {
		ans = chon;
		return;
	}
	for (int i = 0; i < v[a].size(); i++) {
		int x = v[a][i];
		if (!visited[x]) {
			dfs(x, b, chon+1);
		}
	}
}

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

	dfs(a, b, 0);

	if (ans)  cout << ans;
	else cout << -1;
}