[BOJ/C++] 2644 촌수계산

문제

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

풀이

그래프에서 depth 계산하는 문제! DFS / BFS 둘 다 풀이 가능하다.

📍DFS

재귀 호출
2->7 가고, 7에서 더 이상 갈 데가 없어서
2로 돌아가 2->8 이런 식으로 되는데 계속 count가 올라가는 줄 착각함

📍BFS

풀이 자체는 간단한데 depth 배열 호출 방식을 이해하는데 애 먹음..

코드

DFS / BFS 방식 둘 다 포함되어 있음

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<int> v[101];
bool check[101];
int depth[101];
int ans = -1;

void dfs(int node, int target, int depth_cnt) {
	check[node] = true;

	if (node == target) {
		ans = depth_cnt;
		return;
	}

	for (int i = 0; i < v[node].size(); i++) {
		int next = v[node][i];

		if (!check[next]) {
			dfs(next, target, depth_cnt+1);
		}
	}
}

void bfs(int node, int target) {
	queue<int> q;

	q.push(node);
	check[node] = true;

	while (!q.empty()) {
		int cur = q.front();

		q.pop();

		for (int i = 0; i < v[cur].size(); i++) {
			int next = v[cur][i];

			if (!check[next]) {
				check[next] = true;
				q.push(next);
				depth[next] = depth[cur] + 1; //depth 계산
			}

			if (next == target) {
				cout << depth[target];
				return;
			}
		}
	}

	cout << "-1";
}

int main() {
	int n, m, t1, t2;
	cin >> n >> t1 >> t2 >> 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(t1, t2, 0);
	cout << ans;

	//bfs(t1, t2);
}