[BAEKJOON] 13032번 : ABCDE(JAVA)

- 알고리즘 분류 : DFS, 백트래킹

- 사용 언어 : JAVA

- 문제 요점

1. 사람 수 N과 친구 관계 수 M을 입력받고 인접 리스트 형태로 그래프를 구성
2. 각 정점(사람)에서 DFS를 시작하여 깊이 5가 되는지(=A-B-C-D-E 관계가 있는지) 탐색
3. DFS에서는 방문 배열을 사용해 방문한 노드를 다시 방문하지 않도록 하며, 백트래킹을 적용
4. 깊이가 5가 되면 결과를 1로 설정하고 탐색을 종료
5. 모든 탐색 후 결과를 출력하며, 깊이 5가 발견되면 탐색 종료

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 {
    static int N, M;
    static List<List<Integer>> graph = new ArrayList<>();
    static boolean[] visited;
    static int result = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        visited = new boolean[N];
        for (int i=0; i<N; i++) {
            graph.add(new ArrayList<>());
        }

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

            graph.get(p1).add(p2);
            graph.get(p2).add(p1);
        }

        for (int i=0; i<N; i++) {
            visited = new boolean[N];
            visited[i] = true;
            dfs(i, 0);

            if (result == 1) {
                break;
            }
        }

        System.out.println(result);
    }

    static void dfs(int now, int count) {
        List<Integer> nextList = graph.get(now);
        count++;
        if (count == 5) {
            result = 1;
            return;
        }

        for (int i=0; i<nextList.size(); i++) {
            int nextIdx = nextList.get(i);
            if (!visited[nextIdx]) {
                visited[nextIdx] = true;
                dfs(nextIdx, count);
                visited[nextIdx] = false; // 백트래킹
            }
        }
    }
}