[백준] 13023번 ABCDE

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

13023번: ABCDE

한 배열 리스트에 4개 이상이 쌓이면 관계가 존재하는 것

 

import java.util.*;
import java.io.*;

public class Main {

    static int n, m;
    static List<Integer>[] list;
    static boolean[] visit;


    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        // 사람 수
        n = sc.nextInt();
        // 친구 관계 수 
        m = sc.nextInt();

        list = new ArrayList[n];
        for(int i=0; i < n; i++) {
        	list[i] = new ArrayList<>();
        }   

        for(int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();

            list[a].add(b);
            list[b].add(a);
        }

        for(int i = 0; i < n; i++){
            visit = new boolean[n];
            dfs(i, 0);
        }
        System.out.println(0);
    }

    public static void dfs(int start, int depth) {
        if(depth == 4) {
            System.out.println(1);
            System.exit(0);
        }

        visit[start] = true;
        for(int i = 0; i < list[start].size(); i++) {
            int temp = list[start].get(i);
            if(!visit[temp]) {
                visit[temp] = true;
                dfs(temp, depth + 1);
                visit[temp] = false;
            }
        }
    }

}