드디어 풀었다..

백준 13023

1. 인사이트

1. ArrayList에 Initital Capacity를 초기에 잡아줘도 실제 size는 0이다.

ArrayList<Integer> a = new ArrayList<>(3);
System.out.println(a.size());

...
0

2. 위 13023같은 문제는 모든 노드를 출발점으로 하여 DFS를 하기 때문에, 2차원 연결 정보 그래프보다 ArrayList를 사용하는 것이 TLE(Time limit Exceeded)를 방지할 수 있다.

2. 전체 풀이

// 백준 13023

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

public class P25 {
    static boolean flag = true;
    static ArrayList<ArrayList<Integer>> graph;
    static boolean[] vst;
    static int cnt = 5;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N, M;

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

        graph = new ArrayList<>(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 a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        for (int i = 0; i < N; i++) {
            if (!flag) break;

            else {
                vst = new boolean[N];
                vst[i] = true;
                DFS(i, 1);
            }
        }


        if (flag) {
            bw.write(0 + "");
        } else {
            bw.write(1 + "");
        }

        bw.flush();
        bw.close();

    }

    static void DFS(int n, int dep) {

        if (!flag) {
            return;
        }
        if (dep == cnt) {
            flag = false;
            return;
        }

        for (int i : graph.get(n)) {
            if (vst[i] == false) {
                vst[i] = true;
                DFS(i, dep + 1);
                vst[i] = false;
            }
        }

    }
}