[백준] ABCDE 13023번 C++ 풀이

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

13023번: ABCDE

#include <iostream>
#include <vector>
using namespace std;
bool visit[2001];
int res = 0;
int N,M;
vector<int> v[2001];
void DFS(int cur, int cnt)
{
	if (cnt == 5) // A,B,C,D,E 5명이 연결이 되었으므로 가능함
	{
		res = 1;
		return;
	}

	for (int i = 0; i < v[cur].size(); i++)
	{
		if (visit[v[cur][i]] == false)
		{
			visit[v[cur][i]] = true;
			DFS(v[cur][i], cnt + 1);
			visit[v[cur][i]] = false;
		}
	}

}

int main(void)
{
	cin >> N>>M;
	for (int i = 0; i < M; i++)
	{
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for (int i = 0; i < N; i++) {
		visit[i] = true;
		DFS(i, 1);
		if (res == 1)
			break;
		visit[i] = false;
	}
	cout << res;
}

 

처음에 무슨 모든 N명의 친구가 이어져야하는줄 알았는데

그냥 5명만 이어질 수 있는지를 묻는 문제였었다...

 

그리고 제출 했더니 시간초과가...!

그래서 그냥 이미 답이 res=1 로 가능하다는 판명이 났다면 더이상 더 탐색을 하지 않기로 했더니 정답이 되었다.

if (res == 1)
	break;