[백준] 2644번 촌수계산

2644번: 촌수계산

BFS와 재귀로 풀었다.

x, y의 촌수를 구해야 할 때 x를 루트로 잡고

x부터 y가 나올 때까지 BFS 해주었다.

만약 y를 만나지 못한다면 -1을 출력했다.

 

무방향 그래프이므로 입력받을 때

벡터[x]=y, 벡터[y]=x

둘 다 값을 넣어준다.

 

BFS 해줄 때 다음 노드로 넘어갈 때마다 촌수를 +1 해주었고

현재 노드와 연결된 모든 노드들을 검사한 후(검사하는 노드마다 방문 체크)

검사가 다 끝나면 이전 노드로 돌아가기 전에 촌수를 -1 해주었다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector <int> v[101];
int RES = 0, res = 0, finish = 0, visited[101] = { 0 };
void Bfs(int x, int y) {
	if (finish) return;
	queue <int> q;
	if (x == y) {
		finish = 1;
		RES = res;
		return;
	}
	while (!v[x].empty()) {
		if (!visited[v[x].back()]) q.push(v[x].back());
		v[x].pop_back();
	}
	if (q.empty()) return;
	res++;
	while (!q.empty()) {
		visited[q.front()] = 1;
		Bfs(q.front(), y);
		q.pop();
	}
	res--;
}

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

	visited[x] = 1;
	Bfs(x, y);

	if (finish) cout << RES;
	else cout << "-1";

	return 0;
}