[BOJ][Java] 13023번 ABCDE

문제 설명

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

 

이 문제는 5개 이상의 정점이 이어져있는지를 묻는 문제이다.

모든 경우의 수를 다 봐야 하며 정점(사람의 수) = 최대 2000

간선(친구관계의 수) = 최대 2000 이기 때문에

 

만약 모든 정점을 기준으로 DFS 탐색을 실시한다고 하면 O((2000 + 2000) * 2000)으로 시간복잡도상 충분히 

시간 내에 풀 수 있다.

 

추가로 가지치기를 통해서 연산량을 줄이고

단순 DFS를 이용하면 풀 수 있다.

 

package boj;

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


public class BOJ13023 {
    static List<List<Integer>> graph = new ArrayList<>();
    static boolean check = false;
    static boolean[] visited;
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        for(int i = 0; i < N; i++){
            graph.add(new ArrayList<>());
        }

        visited = new boolean[N];

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

            graph.get(u).add(v);
            graph.get(v).add(u);
        }

        for(int i = 0; i < N; i++){
            if(check) break;
            dfs(i,1);
        }

        System.out.println(check ? "1" : "0");

    }

    static void dfs(int now, int depth){
        if(depth == 5 || check){
            check = true;
            return;
        }

        visited[now] = true;
        for(int num: graph.get(now)){
            if(!visited[num]){
                dfs(num,depth+1);
            }
        }
        visited[now] = false;
    }
}