[c++/백준] 2644번: 촌수계산

문제 링크

2644번: 촌수계산

풀이

DFS로 푸는 문제

1. 입력을 받으며 arr의 인덱스에 연결된 노드들을 넣는다.
   n1랑 n2입력 받으면 arr[n1]에 n2를 넣고, arr[n2]에 n1를 넣는다.
2. 방문처리를 하고 DFS 함수 호출을 한다.
3. n 인덱스에 있는 노드들을 보면서 방문을 했으면 continue, 아니면 방문처리 후 재귀호출한다. 다른 노드에서 진입할 수도 있으므로 visit은 다시 0으로 해준다.
   3-1. n이 n2와 같다면 촌수 계산이 끝난 것이므로 answer를 갱신해준다.
4. answer가 0이면 방문이 안된다는 의미이므로 -1, 아니면 answer를 출력한다.

코드

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

vector<int> visit;
int n1, n2;
int answer;

void DFS(int n, int cnt, vector<vector<int>> &arr)
{
	if (n == n2)
	{
		answer = cnt;
		return;
	}
	for (int i = 0; i < arr[n].size(); i++)
	{
		if (visit[arr[n][i]]) continue;
		visit[arr[n][i]] = 1;
		DFS(arr[n][i], cnt + 1, arr);
		visit[arr[n][i]] = 0;
	}
}

int main(void)
{
	int n;
	cin >> n;
	vector<vector<int>> arr(n + 1);
	visit.resize(n+1);

	cin >> n1 >> n2;
	
	int m;
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		int n1, n2;
		cin >> n1 >> n2;
		arr[n1].push_back(n2);
		arr[n2].push_back(n1);
	}

	visit[n1] = 1;
	DFS(n1, 0, arr);
	if(answer!=0) cout << answer << endl;
	else cout << -1 << endl;

	return 0;
}