[BOJ] 2644 : 촌수계산

Question

---

Solution

• 서로간의 노드를 양방향으로 이어준다.
• 시작 지점 parent에서 끝 지점 child까지 탐색을 시작한다.
• 방문하면 weight 가중치를 더하고 막혀서 되돌아가면 감소시킨다.
• 시작 지점과 끝지점이 같아지면 weight를 반환시키고 출력한다. (단, 찾지못하여 0인 상태로 끝나면 -1을 출력한다.)

---

Cord

#include <iostream>
#include <vector>

#define MAX 101

using namespace std;

int n, m;
int parent, child;
int weight;

bool visited[MAX];
vector<int> v[MAX];

void dfs(int _start, int _end, int _weight)
{
	if (_start == _end)
	{ 
		weight = _weight;
		return; 
	}

	visited[_start] = true;

	for (int i = 0; i < v[_start].size(); i++)
	{
		int next = v[_start][i];
		if (!visited[next])
		{
			_weight++;
			dfs(next, _end, _weight);
			_weight--;
		}
	}
}

int main()
{
	// 사람수, 서로 다른 두 사람의 번호, 관계의 수 입력
	cin >> n;
	cin >> parent >> child;
	cin >> m;

	// 연결
	for (int i = 0; i < m; i++)
	{
		int x, y;
		cin >> x >> y;

		v[x].push_back(y);
		v[y].push_back(x);
	}

	// dfs 실행
	dfs(parent, child, 0);
	
	// 출력
	if (weight == 0) { cout << -1; }
	else { cout << weight; }

	return 0;
}

---

Result