[백준] 알고리즘 2644번 - 촌수계산 문제

#include <bits/stdc++.h>
using namespace std;
vector<int> v1[101];
bool check[101];
int n,ans = 0;
void dfs(int x,int y,int cnt) {
	check[x] = true;
	if (x == y) {
		ans = cnt;
		return;
	}
	int size = v1[x].size();
	for (int i = 0; i < size; i++) {
		if (check[v1[x][i]] == false && v1[x][i] != 0) {
			dfs(v1[x][i], y, cnt + 1);
		}
	}
}
int main(){
   ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
   int p1, p2,m;
   cin >> n >> p1 >> p2>>m;
   for (int i = 0; i < m; i++) {
	   int x, y;
	   cin >> x >> y;
	   v1[x].push_back(y);
	   v1[y].push_back(x);
   } 
   dfs(p1,p2,0);
   if (ans == 0) cout << -1;
   else cout << ans;
}

DFS, BFS 둘다 이용하여 문제를 해결 할 수 있다.

하지만 DFS가 촌수를 찾기 위해선 깊이 탐색해야 할 것 같기에 DFS로 구현해보았습니다.

전체를 DFS 하려고 하지마라

저는 처음에 전체를 DFS해서 문제를 해결하여 촌수를 구하면 되지않을까라고 생각하였습니다.

하지만 그렇게되면 촌수계산이 엉망으로 되기때문에 입력받는 P1,P2를 이용하여 촌수를 계산합니다.

이 그림을 직접 그려보았는데, 이걸 이해하시면 쉽게 해결할 수 있을겁니다.