[백준] | JAVA, 자바 | 13023번 - ABCDE

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

---

문제 풀이 :

1. 사람의 수 N, 친구 관계의 수 M 입력받기

2. M만큼 친구 관계 입력받기

3. A, B, C, D, E 관계가 성립하는지 확인

4. 관계가 존재한다면 1, 존재하지 않는다면 0 출력

---

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 {
    private static int N, M;
    private static List<Integer>[] list;
    private static boolean[] visited;
    private static boolean found;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 1. 사람의 수 N, 친구 관계의 수 M 입력받기
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

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

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            // 2. 친구 관계를 M 만큼 입력받고 양방향 리스트에 저장
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            list[a].add(b);
            list[b].add(a);
        }

        visited = new boolean[N];
        found = false;
        // 3. dfs 탐색
        for (int i = 0; i < N; i++) {
            dfs(i, 1);
            if (found) break; // 만약 found가 true라면 종료
        }
        // 4. A,B,C,D,E 관계가 존재하면 1, 없으면 0 출력
        System.out.println(found ? 1 : 0);
    }

    private static void dfs(int node, int cnt) {
        // 3-1. cnt가 5, 방문 횟수가 5가 되면 종료
        if (cnt == 5) {
            found = true;
            return;
        }

        visited[node] = true;
        for (int next : list[node]) {
            if (!visited[next]) {
                dfs(next, cnt + 1);
                if (found) return; // 이미 찾았으면 더이상 탐색하지 않음
            }
        }
        // 백트래킹
        visited[node] = false;
    }
}