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

2644번: 촌수계산 (acmicpc.net)

2644번: 촌수계산

---

난이도 : 실버 2

 

 

 

문제 설명 :

촌수를 구하는 문제였습니다. DFS와 BFS를 이용하여 구할 수있습니다.

 

코드 설명:

DFS함수의 인자로 now, end, num을 받습니다.

now와 end는 구하려는 가족의 넘버이며, num은 촌수계산을 위한 변수입니다.

dfs를 돌면서, 방문하지 않은 노드면 num에 +1을 해주고 둘이 가족(연결되어있으면)이면 num을 출력합니다.

둘이 다른 가족이면 ans은 0이되서 -1이 출력되게합니다.

 

문제 예시로 7과 3의 촌수를 계산하는 것이 나왔는데,

코드 실행을 그대로 적어보면

now = 7 이므로 7에는 2의 노드가 있으므로 next = 2가되고 num =1

now = 2가 되면 2에는 1, 7, 8, 9와 연결되어있는데, next = 1이 되면 num = 2

now = 1이 되면 1에는 2와 3이 연결되어있으므로 next = 3(2는 방문했으므로) num = 3

이 되어 3을 출력하게 됩니다.

 

다른 예시로 8과 9의 촌수를 계산해볼 수있는데(제일 헷갈렸던 부분)

8이 들어오고

next= 2, num =1

->( next = 1, num=2 ), (next = 7, num = 2), (next = 8, num =2), (next = 9, num =2)

next가 1일 때 next가 1로가고 , 3으로 가면 여쪽부분 재귀는 종료,

next가 7일 때는 next가 2가되는데, 2는 방문했던 노드이므로 이쪽 재귀도 종료

8도 마찬가지 따라서 9일때 num =2가되어 출력이 되는 것입니다.

 

글로 설명하니까 굉장히 복잡해보이네요,,, 코드 보시고 직접 디버깅 해보시면 이해가 가실 겁니다!!

 

코드 :

#include <iostream>
#include <algorithm> 
#include <vector>
using namespace std;

int n, m, ans;
vector<int> v[101];
int visited[101];


void dfs(int now, int end, int num) {
	visited[now] = 1;
	if (now == end) {
		ans = num;
	}
	for (int i = 0; i < v[now].size(); i++) {
		int next = v[now][i];
		if (!visited[next]) {
			dfs(next, end, num+1);
		}
	}
}

int main() {
	int x, y;
	cin >> n >> x>> y>> m;


	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
    
    //코드이해를 위해 정렬했습니다 아래 부분은 빼도됨
	for (int i = 1; i <= n; i++) {
		sort(v[i].begin(), v[i].end());
	}
	
	dfs(x, y,0);
	if (ans != 0) {
		cout << ans;
	}
	else cout << "-1";

}