[JAVA] 백준 13023번: ABCDE ( 초급 2-35 ) - fail

문제

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

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

• A는 B와 친구다.
• B는 C와 친구다.
• C는 D와 친구다.
• D는 E와 친구다.

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

입력

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

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

출력

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

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;
import java.util.StringTokenizer;

public class baekjoon13023_2 {
    private static boolean[] visit;
    private static int isTrue = 0;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int vertex = Integer.parseInt(st.nextToken());
        int edge = Integer.parseInt(st.nextToken());

        visit = new boolean[vertex];
        ArrayList<ArrayList<Integer>> info = new ArrayList<>();

        // 어레이 리스트 초기화
        for (int i = 0; i < vertex; i++) {
            info.add(new ArrayList<>());
        }

        // 양방향 간선 정보 입력
        for (int i = 0; i < edge; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            info.get(from).add(to);
            info.get(to).add(from);
        }

        // 정점마다 모든 간선 확인
        for (int i = 0; i < vertex; i++) {
            visit[i] = true;
            dfs(info, i, 1);
            visit[i] = false;
        }

        System.out.println(0);
    }

    private static void dfs(ArrayList<ArrayList<Integer>> info, int currentVertex, int index) {
        if (index == 5) {
            System.out.println(1);
            System.exit(0);
            return;
        }
        for (int nextVertex : info.get(currentVertex)) {
            if (!visit[nextVertex]) {
                visit[nextVertex] = true;
                dfs(info, nextVertex, index + 1);
                visit[nextVertex] = false;
            }
        }
    }
}