문제

풀이 과정

완전 탐색 문제. 문제를 이해하는 게 어려웠던 문제이다.
이해하는데 어려운 부분이 바로 이 부분이었다.

저 위의 부분을 해석하자면 즉, 어떤 임의의 값으로 시작했을 때 쭉 이어져 depth 가 5까지 나올 수 있냐를 찾는 문제이다.

나의 경우는 DFS 를 활용하였고 문제 풀이 방식은 다음과 같다. 더불어 시간초과를 만드는 요소도 존재하니, 어느정도의 최적화 작업도 해주어야 한다.

1. a→b→c→d→e 총 5개 이상의 depth를 이루는 경로를 찾는 문제.
2. 각 node를 시작으로 DFS 실행
3. 시간복잡도가 어느정도인지는 모르겠으나, 시간 초과 있음. 시간 초과를 줄일 만한 부분을 생각해야함
   3-1. 한 경우에서 5 이상의 depth가 나오면 즉시 리턴하도록 함
4. DFS 진행시 해당 경로 탐색 시 5이상의 경로가 아니라면, 방문처리를 다시 false로 바꾸어서 다음 경로에서 사용할 수 있도록 만들어 줄 것!

3번이 바로 시간초과를 발생할 수 있는 요소를 개선하는 방안이다.

4번이 직접 테케를 만들어봐야만 알 수 있어서 문제 푸는 시간을 오래잡아 먹었다. 아직도 완전 탐색이 익숙치 않나 보다.

정답

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

public class Main {
    static List<Integer> adjList[];
    static boolean[] visited;
    static int ans;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

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

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken());
            int n2 = Integer.parseInt(st.nextToken());
            adjList[n1].add(n2);
            adjList[n2].add(n1);
        }

        for (int i = 0; i < N; i++) {
            ans = 1;
            visited = new boolean[N];
            DFS(i, ans);
            if(ans >= 5) {
                System.out.println(1);
                return;
            }
        }
        System.out.println(0);
        br.close();
    }

    private static void DFS(int idx, int cnt) {
        if(visited[idx]) return;
        if(cnt >= 5 || ans >= 5) {
            ans = 5;
            return;
        }

        visited[idx] = true;
        for(Integer nNode : adjList[idx]) DFS(nNode, cnt+1);
        visited[idx] = false;
    }
}