백준 13023번 ABCDE

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

13023번: ABCDE

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main_13023_유동훈 {

	static int answer;
	static int N;
	static int M;
	static List<Integer>[] list;
	static int[] visit=new int[2001];
	
	
	/*
	 * 친구 4개만 찾으면 정답!
	 * count => 찾은친구 개수
	 */
	static void dfs(int parent, int count)
	{
		//1.부모 방문처리
		visit[parent]=1;
		
		//친구4명 찾음->정답->종료
		if(count==4)
		{
			System.out.println(1);
			System.exit(0);
		}
		
		//2.연결된 자식에 대해
		for(int i=0; i<list[parent].size();++i)
		{
			//3.자식방문안함 ->자식방문, 친구+1
			if(visit[list[parent].get(i)]==0)
				dfs(list[parent].get(i),count+1);
		}
		
		//끝나면 미방문처리
		visit[parent]=0;
			
	}
	
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st;
		st=new StringTokenizer(br.readLine());
		N=Integer.parseInt(st.nextToken());
		M=Integer.parseInt(st.nextToken());

		
		//리스트 초기화, 할당
		list = new ArrayList[N];
		for (int i = 0; i < N; i++) {
			list[i] = new ArrayList<>();
		}

		for(int i=0;i<M;++i)
		{
			st=new StringTokenizer(br.readLine());
			int a= Integer.parseInt(st.nextToken());
			int b= Integer.parseInt(st.nextToken());

			list[a].add(b);
			list[b].add(a);
		}
		
		//모든노드에 대해 (0~n-1) 친구4명 찾기
		for(int i=0;i<N;++i)
			dfs(i,0);
		
		System.out.println(0);
	}

}