[JAVA] 백준 13023번- ABCDE

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

13023번: ABCDE

 

 

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

public class Main{

    static int n, m;
    static ArrayList<ArrayList<Integer>> list;
    static boolean[] visit;
    static int answer = 0;
    public static void dfs(int v, int cnt)
    {
        if(cnt == 5)
        {
            System.out.println(1);
            System.exit(0);
            return;
        }

        for(int nv : list.get(v)){
            if(visit[nv]) continue;

            visit[nv] = true;
            dfs(nv, cnt+1);
            visit[nv] = false;
        }
    }
    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());
         list = new ArrayList<ArrayList<Integer>>();
         visit = new boolean[n];

         for(int i=0; i<n; i++){
             list.add(new ArrayList<Integer>());
         }

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

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


        for(int i=0; i<n; i++){
            visit[i] = true;
            dfs(i, 1);
            visit[i] = false;
        }
        System.out.println(answer);
    }
}

 

 

처음엔 배열로 입력받아 시간초과가 났다.  cnt == 5가 되었을 때 바로 System.exit(0)으로 종료를 해줘도 시간초과가 났다. 

배열로 한다면 배열의 값인 노드를 찾기 위해 for문에서 0부터 n-1까지 모든 원소를 탐색해야 한다.

ArrayList로 할 경우 친구인 노드들만 add로 저장했으므로, 탐색해야하는 노드가 훨씬 줄어들어 시간이 적게 걸리게 된다.

이렇게 정점의 개수가 많아질 경우에는 ArrayList 를 사용하는게 효율적이다.