[백준/BOJ] 백준 13023번 : ABCDE

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

13023번: ABCDE

 

어떤 사람으로부터 출발해서, dfs(깊이 우선 탐색)을 통해 총 5명(출발 사람 포함)의 사람에 방문할 수 있으면, 친구 조건을 만족하는 것으로 문제를 해결했다

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, m;
vector<int> adj[2005];
int visited[2005];
int result = 0;

void dfs(int here, int cnt) {
	visited[here] = 1;

	if (cnt == 5) {
		visited[here] = 0;
		result = 1;
		return;
	}

	for (int i = 0; i < adj[here].size(); i++) {
		int there = adj[here][i];

		if (visited[there] == 0) {
			dfs(there, cnt + 1);
		}
	}

	visited[here] = 0;
}

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

	cin >> n >> m;

	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, 1);

		if (result == 1) {
			break;
		}
	}

	cout << result;

	return 0;
}