[성실코딩 15일차] 백준 #2644 촌수계산 / DFS

헤헤 깔끔하게 풀려서 기분이 좋다

조건들 하나하나 고려하면서 코드짜는 연습하기!!

#include <iostream>
#include <vector>

using namespace std;

int n; // 사람 인원
vector<vector<int>> arr; // 친척 관계
int visited[101]; // 노드에 방문했는지
int a1, a2;// a1과 a2의 관계
int result = -1; //촌수
// 자기 자신 방문했을 때도 촌수를 증가시켜주므로, 
// 0이 아니라 -1에서 시작.

bool dfs(int _a) { // _a: 사람 번호
	result++; // 촌수 증가
	visited[_a] = 1; // 방문표시
	if (_a == a2) { // 원하는 사람이 나오면
		return true;
	}
	// 원하는 사람이 아니면
	// 연결된 노드들 확인.
	for (int i = 0; i < arr[_a].size(); i++) {
		if (visited[arr[_a][i]] == 0) { // 방문한 이력이 없을 때만
			if (dfs(arr[_a][i]) == true) {
				// 원하는 사람 찾으면
				// 함수 끝내기
				return true;
			}
			else {
				// 원하는 사람 찾지 못했으면
				// 촌수 다시 감소시키고, 다른 노드들 검사.
				result--;
			}
		}
	}
	// 모든 노드들 방문했는데 원하는 사람 찾지 못하면
	return false;
}

int main() {

	// 입력
	cin >> n;
	arr.assign(n+1,vector<int>(0, 0));
	cin >> a1 >> a2; 
	int tc;
	cin >> tc;
	for (int i = 0; i < tc; i++) {
		int x, y; // 부모, 자식
		cin >> x >> y;
		arr[x].push_back(y);
		arr[y].push_back(x);
	}

	// 연산 
	if (dfs(a1) == false) {
		// 원하는 사람과의 관계 찾지 못했을 때는
		// -1 출력
		result = -1;
	}

	// 출력
	// 원하는 사람과의 관계 찾으면 result 그대로 출력
	cout << result;

	return 0;
}