[백준 13023] ABCDE(Java)

문제 링크 : https://www.acmicpc.net/problem/13023

이 문제는 dfs를 이용하여 풀 수 있습니다. 문제를 주의깊게 읽어보면 친구 관계를 가진 사람이 5명만 존재하면 된다는 것을 알 수 있습니다. 따라서 dfs로 깊이가 5가 되었을 경우 break 하는 방식으로 진행합니다. 여기서 주의할 점은 이미 발견한 이후 다른 탐색을 진행할 경우 시간 초과가 발생할 수 있으니 발견한 즉시 모든 탐색을 멈추고 바로 결과를 출력합니다.

다음은 코드입니다.

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

class Main{
    static int N,M;
    static boolean[] check;
    static boolean exist = false;
    static List<Integer>[] graph;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        check = new boolean[N];
        graph = new List[N];
        for(int i=0;i<N;i++) graph[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());
            graph[a].add(b);
            graph[b].add(a);
        }

        for(int i=0;i<N;i++){
            check[i] = true;
            dfs(i,1);
            if(exist) break;
            check[i] = false;
        }
        System.out.println(exist ? 1 : 0);
    }

    static void dfs(int curr, int dpt){
        if(dpt == 5 || exist){
            exist = true;
            return;
        }

        for(int next : graph[curr]){
            if(!check[next]){
                check[next] = true;
                dfs(next,dpt+1);
                check[next] = false;
            }
        }
    }
}