[BAEKJOON] 2644번 촌수계산

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

2644번: 촌수계산

문제조건

1. 부모 자식들간의 관계가 주어졌을때, 계산하고자 하는 두사람의 촌수를 구해라

접근방법

 

트리 모양 구조를 탐색하는 그래프 탐색 방법으로 접근했다.

근데 촌수 이므로 cycle이 생길 일은 없다.

따라서 각 노드를 양방향 연결해주고 DFS로 탐색해줬다. 아버지의 형제들과 나와의 관계는 3촌으로 분류할 수 있는데, 이를 계산하는 방식은 

나 → 아버지(1촌) → 할아버지(2촌) → 아버지형제(3촌)

이런식으로 계산되므로 DFS가 적합하다고 생각했다. 그리고 예외상황으로는 촌수를 계산할 수 없을 경우인데, DFS를 돌리고 한사람을 찾지 못하면 bool타입 변수를 두어 처리해줬다.

 

소스코드

#include <iostream>
using namespace std;

int n, m;
int a, b, relation[101][101], visited[101];
int res = -1;
bool pos = false;

void dfs(int s, int e, int cnt){
	visited[s] = 1;
	if(s == e){
		res = cnt;
		pos = true;
		return;
	}
	for(int i = 1; i <= n; i++){
		if(!visited[i] && relation[s][i] == 1){
			dfs(i, e, cnt+1);
			if(pos) break;
		}
	}
	return;
}

int main(){
	cin >> n;
	cin >> a >> b;
	cin >> m;
	for(int i = 1; i <= m; i++){
		int n1, n2;
		cin >> n1 >> n2;
		relation[n1][n2] = 1;
		relation[n2][n1] = 1;
	}
	dfs(a,b,0);
	cout << res;
}