주어진 두 사람의 촌수를 계산하는 문제.
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;
}