[BOJ] 2644 촌수계산 C++

개요

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

2644번: 촌수계산

실버급 DFS 및 BFS 기본 문제다.

본문

풀이

연습해 볼 겸 인접행렬로 구현해 봤다.

스택을 활용한 DFS로 풀려고 한참 고민했는데, 카운트하는 부분에서 계속 막혔다.

그래서 재귀로 DFS를 구현했더니 바로 풀렸다,,내 시간

스택으로도 풀 수 있을 것 같은데 조금 더 복잡해질 듯하다.

주의할 점으로는 연결되지 않는 상황(-1 출력)을 고려해야 한다.

코드

#include<iostream>
#include<algorithm>
using namespace std;
constexpr int RANGE = 102;

bool fam[RANGE][RANGE]{};
bool visited[RANGE]{};
int from, to;
int n, m;
int ans = -1;

void dfs(int v, int cnt) {
	if (v == to) {
		ans = cnt;
		return;
	}
	for (int i = 1; i <= n; i++)
	{
		if (fam[v][i] && !visited[i])
		{
			visited[i] = true;
			dfs(i, cnt + 1);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> from >> to >> m;

	for (int i = 1; i <= m; i++)
	{
		int x, y;
		cin >> x >> y;
		fam[y][x] = fam[x][y] = true;
	}
	dfs(from, 0);
	cout << ans;
}