백준 Gold 5 ABCDE

ABCDE (백준 Gold 5)

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

친구의 관계가 연속해서 5번 이어질 수 있는지를 체크하는 문제

풀이 방법

재귀와 백트래킹을 통하여 가능한 모든 경우의 수를 테스트
해당 방식으로 문제를 풀 수 있다!

• unordred_map<int,vector>를 통해
  해당 사람의 친구관계를 관리
  

제출 코드

#include<iostream>
#include<vector>
#include<unordered_map>

using namespace std;

int n, m;
const int depth = 5;

bool dfs(unordered_map<int, vector<int>>& fmaps, vector<bool>& visited, int now, int count)
{
	if (visited[now])
		return false;

	visited[now] = true;

	if (count == depth)
	{
		return true;
	}

	if (fmaps.find(now) != fmaps.end())
	{
		for (int next : fmaps[now])
		{
			if (dfs(fmaps, visited, next, count + 1))
				return true;
		}
	}

	visited[now] = false;

	return false;
}

int main()
{
	cin >> n >> m;

	unordered_map<int, vector<int>> fmaps;

	for (int i = 0; i < m; i++)
	{
		int s, t;
		cin >> s >> t;
		fmaps[s].push_back(t);
		fmaps[t].push_back(s);
	}

	vector<bool> visited(n + 1);

	for (int i = 0; i < n; i++)
	{
		if (dfs(fmaps, visited, i, 1))
		{
			cout << 1;
			return 0;
		}
	}

	cout << 0;
	return 0;
}

결과