[BOJ/C++] 13023 ABCDE

문제의 조건은 다음과 같습니다. N명이 있을때

A와 B는 친구이다.
B와 C는 친구이다.
C와 D는 친구이다.
D와 E는 친구이다.

의 조건을 만족하면 됩니다. 연속된 친구의 관계가 5명이면 됩니다.

DFS를 이용하여 문제를 해결할 수 있습니다.

주어진 모든 노드에 대해 DFS를 실행하고 깊이가 5에 도달했다면 1을 출력하고 아니라면 0을 출력하면 됩니다.

// boj g5 13023
// ABCDE

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

static vector<vector<int>> G;
static vector<bool> visited;

static bool arrived = false;
void DFS(int v, int depth);


int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;
	cin >> N >> M;
	
	G.resize(N);
	visited = vector<bool>(N, false);

	for(int i=0; i<M; i++)
	{
		int v, e;
		cin >> v >> e;
		G[v].push_back(e);
		G[e].push_back(v);
	}

	for (int i = 0; i < N; i++)
	{
		DFS(i, 1);
		if (arrived)
		{
			cout << 1;
			return 0;
		}
	}
	cout << 0;

	return 0;
}

void DFS(int v, int depth)
{
	if(depth==5 || arrived)
	{
		arrived = true;
		return;
	}
	visited[v] = true;

	for(int i: G[v])
	{
		if (!visited[i])
			DFS(i, depth + 1);
	}
	visited[v] = false;
}