문제풀이
- 촌수를 계산하기위해 사람을 정점, 부모 자식관계를 간선으로 생각했다.
- 그래프 탐색은 가장 짧은 동선을 찾기 편한 BFS로 탐색을 진행했다.
- 노드를 한단계식 더 탐색해 나갈때마다 cnt를 한개씩 올렸고, 목적하는 노드가 나오면
그 cnt를 ans에 저장했다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <math.h>
#include <string>
#include <string.h>
#include <queue>
using namespace std;
#define endl "\n"
#define MAX 100+1
int n, m;
int target1, target2;
vector<int> graph[MAX];
bool visited[MAX];
int ans;
queue<int> q;
void bfs(int v,int cnt) {
if (v==target2)
{
if (ans<=cnt)
{
ans = cnt;
}
}
visited[v] = true;
q.push(v);
while (!q.empty()) {
int w = q.front();
q.pop();
for (auto k : graph[w]) {
if (!visited[k])
{
bfs(k,cnt+1);
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
//ifstream cin; cin.open("input.txt");
cin >> n;
cin >> target1 >> target2;
cin >> m;
for (int i = 0; i < m; i++)
{
int x, y;
cin >> x >> y;
graph[x].push_back(y);
graph[y].push_back(x);
}
bfs(target1, 0);
if (ans==0)
{
cout << -1;
}
else {
cout << ans;
}
}