[DFS] ABCDE (백준 13023번, 자바)☆☆☆

- N명중에서 5명만 친구관계여도 된다는 것 !!!
- 각 사람이 4번 이상의 연결이 이루어져야 한다.
- 관계의 가중치가 주어지지 않음 -> BFS보다 DFS

 

 

 

import java.util.*;

class Main
{
	
	static ArrayList<Integer>[] arr;
	static int answer=0;
	static int N;
	static boolean[] visit;
	
	public static void main(String args[]) throws Exception
	{
		
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		int M=sc.nextInt();
		
		arr=new ArrayList[N];
		
		
		for(int i=0;i<N;i++) {
			arr[i]=new ArrayList<Integer>();
			
		}
		for(int i=0;i<M;i++) {
			int a=sc.nextInt();
			int b=sc.nextInt();
			arr[a].add(b);
			arr[b].add(a);
		
		}
		for(int i=0;i<N;i++) {
			visit=new boolean[N];
			dfs(0,i);
			if(answer==1) break;
		}
		System.out.println(answer);
	}
	
	
	static void dfs(int count, int x) {
		if(count>=4) {
			answer=1;
			return;
		}
		
		visit[x]=true;
		for(int i=0;i<arr[x].size();i++) {
			if(!visit[arr[x].get(i)]) {
				dfs(count+1, arr[x].get(i));
				visit[arr[x].get(i)]=false;
			
			}
		}
			
	}
		
}