백준 13023 질문있습니다.

문제의 의도가 파악이 되지 않아 질문 남깁니다.

모든 노드에서 DFS를 돌리는경우도 유튜브 채널 댓글 보면서 이해를 했습니다.

위의 설명을 보니 이해가 바로 되었습니다.

근데 문제에서

• A는 B와 친구다.

• B는 C와 친구다.

• C는 D와 친구다.

• D는 E와 친구다.

라는 것을 보고 깊이가 4일 때를 하드코딩으로 코드에 넣으셨는데 저는 이것을 보고 그냥 DFS로 n -1번까지 다 연결되어 있으면 1을 출력하라는 것이구나~ 하고 이해를 하였는데 어디에 근거하여 깊이가 4인 경우가 발생하면 1을 출력하라고 어떻게 이해하셨는지 궁금합니다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <deque>
#include <cmath>
using namespace std;

#define ll long long
#define endl "\n"

int n; bool flag = false;
vector<vector<int>> adj;
vector<bool> visit;
void DFS(int now, int depth)
{
	visit[now] = true;
	if (depth == n - 1)
	{
		flag = true; return;
	}
	for (int next : adj[now])
	{
		if (visit[next] == false) DFS(next, depth + 1);
	}
	visit[now] = false;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int m; cin >> n >> m; adj.resize(n); visit.resize(n);
	for (int i = 0; i < m; ++i)
	{
		int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a);
	}
	for (int i = 0; i < n; ++i)
	{
		DFS(i, 0); 
		if (flag) break;
	}
	if (flag == false) cout << 0;
	else cout << 1;
	return 0;
}

위는 제가 처음에 짠 틀린 코드입니다. DFS의 조건문에서 depth가 n - 1과 같으면 flag를통해 return하도록 하였습니다.