[C++] 백준 13023번 ABCDE

 

1) 문제설명

백준 Online Judge 13023번 ABCDE

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

13023번: ABCDE

 

2) 아이디어

정점들을 입력하고 모든 정점에서 DFS를 따로따로 돌려주어서 DFS를 실행한 횟수가 4번 이상이면 친구의 친구가 4번있다는 뜻이다.

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;


int visited[2001]={0,};
vector <int> v[2001];
int flag = 0;
int maxt = 0;
void dfs(int x, int cnt) {
	if (visited[x] == 1) { // 방문했다면 리턴
		return ;
	}

	visited[x] = 1; //방문 표시

	if (cnt >= 4) { // dfs를 4번이상 실행했다면 = 친구의 친구가 4번있다면
		flag = 1; // 표시해주고
		return; // 리턴(안하면 시간초과)
	}
	
	for (int i = 0; i < v[x].size(); i++) {// v[0] = 1, 0
		
		dfs(v[x][i], cnt + 1);
	}
	visited[x] = 0; 
	
}

int main() {
	int n, m;
	int arr[2001], brr[2001];
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		
		cin >> arr[i] >> brr[i];
		v[arr[i]].push_back(brr[i]);
		v[brr[i]].push_back(arr[i]);
	}
	for (int i = 0; i < n; i++) {

		dfs(i, 0); // 정점을 처음 시작만 하는게 아니라 모든 정점에서 dfs를 한번씩 해봐야함
		memset(visited, 0, sizeof(visited)); // dfs한번 돌리고 방문기록 초기화
	}
	cout << flag << endl;
	
}