[DFS]백준 2644 촌수계산 C++

https://www.acmicpc.net/problem/2644

2644번: 촌수계산

---

---

풀이 :

기본적인 dfs 문제 입니다.  사람의 번호가 1,2,3,..n명 중 서로 다른 두 사람 x, y가 주어졌을 때 두사람의 촌수를 구하는 문제 입니다. 두 사람 씩 부모-자식 관계가 주어지므로 graph 형식으로 데이터를 표현한 다음에 촌수를 구해야하는 두사람을 시작점 - 끝점으로 깊이 탐색으로 깊이 검색을 해주면 된다!

그래프 내부에서 관계가 없을 때는 -1을 출력해야하기 때문에 외부에서 -1로 미리 초기화 해주면 됨

 

 

코드 :

#include <iostream>
#include <vector>
#define MAX 102
using namespace std;

int n, a, b, m, x, y;
vector<int> graph[MAX];
int visit[MAX];
int rst = -1;

void dfs(int start, int cnt) {
	visit[start] = 1;

	for (int i = 0; i < graph[start].size(); i++) {
		int next = graph[start][i];
		if (next == b) {
			rst = cnt;
			return;
		}
		if (!visit[next]) {
			dfs(next, cnt + 1);
		}
	}
}
int main() {

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

	dfs(a, 1);
	cout << rst << endl;
}