[백준] 촌수계산_2644

📝 문제

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

💻 코드

#include <iostream>
#include <vector>

using namespace std;

int n;
int targetX, targetY;
int m;
vector<int> family[101];
int check[101] = { 0, };
int answer = 0;

void dfs(int start, int cnt) {

	if (start == targetY) {
		answer = cnt;
		return;
	}
	
	for (int i = 0; i < family[start].size(); i++) {
		int next = family[start][i];
		if (check[next]) continue;
		check[next] = 1;
		dfs(next, cnt + 1);
	}
}

int main() {
	cin >> n;
	cin >> targetX >> targetY;
	cin >> m;

	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		family[x].push_back(y);
		family[y].push_back(x);
	}
	check[targetX] = 1;
	dfs(targetX, 0);

	if (answer) cout << answer;
	else cout << -1;

	return 0;
}

💡 Point

촌수는 사람을 몇번 거치는가로 결정된다.
입력 x, y의 관계를 잘 구현해서 dfs로 몇번 거치는지 카운트하면 EASY