1. 문제 설명

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

A는 B와 친구다.
B는 C와 친구다.
C는 D와 친구다.
D는 E와 친구다.
위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

2. 입력

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.

둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

3. 출력

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

4. 문제 풀이

이 문제는 한 번에 이해하기 힘들었다. 아무리 읽어도 이게 뭔 소리지..? 라는 생각이 들어서 노트에 그려보고 질문 게시판을 참고하여서 겨우 이해했는데 이해하고 나니 간단한 문제였다.

이 문제는 사람 5명이 한 번에 연결될 수 있으면 1 , 아니면 0을 반환하면 된다.

즉, 중요한 것은 5명이 연속되게 연결되어야 한다는 점이였다.

그냥 DFS를 돌리면 시간 초과가 나게 되어있기 때문에 백트래킹으로 조건을 하나 주어야 한다.

5. 코드
   //백준 - ABCDE (13023)
   package exercise_coding.backjun.backjun20230404;

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 exam01 {

static List<List<Integer>> graph; //연결관계를 저장할 그래프
static int answer; // 연결된 수를 셀 변수

public static void main(String[] args) throws IOException {
    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());

    graph = new ArrayList<>();

    for (int i = 0; i < N; i++) {
        graph.add(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.get(a).add(b);
        graph.get(b).add(a);
    }

    System.out.println(graph);

    for (int i = 0; i < N; i++) {
    	//방문 여부를 확인할 boolean 배열
        boolean[] visited = new boolean[N];
        visited[i] = true; //시작 사람은 방문 표시
        answer = 0; //answer = 0으로 초기화한다.
        dfs(i, visited);
        System.out.println("answer = " + answer);
        //dfs를 돌아나와 answer가 4이상이면 그대로 끝내면 된다.
        if (answer >= 4) {
            System.out.println(1);
            return;
        }
    }
    System.out.println(0);
}

private static void dfs(int start, boolean[] visited) {
	//앞서 말했던 시간초과가 나지 않게하기 위해 추가한 코드
    //answer가 4이면 끝내야 하기 때문에
    if (answer == 4) {
        return;
    }

    for (int i = 0; i < graph.get(start).size(); i++) {
        if (!visited[graph.get(start).get(i)]) {
            visited[graph.get(start).get(i)] = true;
            answer++; //연결될 때마다 +1 해준다.
            dfs(graph.get(start).get(i), visited);
            if (answer == 4) {
            //연결된 수가 4이면 총 5명이 연결되었기 때문에 종료한다.
                return;
            }

//아니라면 방문 처리를 취소하고 연결 수도 -1 해준다.
visited[graph.get(start).get(i)] = false;
answer--;

        }
    }

}

}