[백준/c++] 13023 ABCDE

문제

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

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

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.

둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

출력

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

구현해야할 조건

그래프를 그려봤을때, DFS가 어울리는 문제인데 MAX가 2000*2000 배열을 만드는 것보다. 각 노드에 엣지를 그려주는 vector를 선택해야한다. 초반에 vector에 대한 생각을 못해서 조금 걸린 문제

code

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

#define MAX 2001
using namespace std;

bool res = false;
bool visited[MAX];

int n,m;
vector<int> v[MAX];
//int check[MAX][MAX];

void DFS(int start, int cnt)
{
	if(cnt == 4)
	{
		res = true;
		return;
	}
	
	for(int i = 0; i < v[start].size(); i++)
	{
		int next = v[start][i];
		
		if(!visited[next])
		{
			visited[next] = true;
			DFS(next, cnt+1);
			visited[next] = false;
		}
	}
	
}

int main()
{
	memset(visited,false,sizeof(visited));
	//memset(check,0,sizeof(check));
	
	cin >> n >> m;
	
	for(int i = 0; i < m; i++)
	{
		int from,to;
		cin >> from >> to;
		v[from].push_back(to);
		v[to].push_back(from);
	}
	
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			visited[j] = false;
		}
		visited[i] = true;
		DFS(i,0);
		if(res)
			break;
	}
	
	cout << res;
	
	return 0;
}