[백준] ABCDE java

1. 문제 설명

문제 링크

문제 설명이 조금 직관적이진 않은데, A는 친구의 친구를 흘러가서 E까지 친구가 된다. 즉 DFS로 했을 때, 깊이가 5까지 가는 관계가 있는지 찾는 문제이다.

2. 접근 방식

문제에 나와 있듯이, 임의의 시작 노드를 선정해서, 거기서부터 깊이가 5인 DFS 재귀가 성립하는 게 있으면 1, 모든 노드를 시작 노드로 두고 해도, 깊이가 5인 재귀가 성립하지 않으면 0을 출력하면 된다.

3. 코드 분석

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static ArrayList<Integer>[] lists;
    static boolean [] isVisited;
    static boolean isValid = false;
    static StringBuilder sb = new StringBuilder();
    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());
        lists = new ArrayList[N];
        isVisited = new boolean[N];

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

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            lists[start].add(end);
            lists[end].add(start);
        }
        for (int i = 0; i < N; i++) {
            isVisited[i] = true;
            dfs(0,i);
            isVisited[i] = false;
            if(isValid) break;
        }
        if(!isValid) System.out.println(0);
        else System.out.println(1);
    }
    public static void dfs(int depth, int vertex) {
        if(depth == 4){
            isValid = true;
            return;
        }

        for (int i = 0; i < lists[vertex].size(); i++) {
            int next = lists[vertex].get(i);
            if(!isVisited[next]){
                isVisited[next] = true;
                dfs(depth+1, next);
                if(isValid) return;
                isVisited[next] = false;
            }
        }
    }
}

4. 성장하기

시간 초과가 날 수 없는 문제에서 시간초과 혹은 틀렸습니다가 났다.
DFS는 최악의 시간복잡도가 O(V+E)로 해당 문제에서는 정점이 최대 2000, 간선이 최대 2000이다. 최악의 경우, 해당 DFS를 모든 노드에 대해 실행해야하니, 4000*2000 = 8000000 이 된다.
근데 나는 2가지 실수를 해서 시간 초과가 났다.

1. 기저 조건의 종료를 depth == 5로 두었다. 그래서 깊이가 6인 것을 찾아야 그만뒀다.
2. 시작 노드를 방문처리하지 않았다.

내 풀이의 경우, 다음 Node 들어가기 전에, 해당 Node를 방문처리하는 형식으로 했다.
그러니까 현재 노드가 아닌, 다음 노드를 true 처리 한 것이다. 이런 식으로 하니, 맨 처음 시작 노드에 대한 방문처리를 빼먹었다.

    public static void dfs(int depth, int now) {
        if(depth == 4 || isValid == true){
            isValid = true;
            return;
        }

        isVisited[now] = true;

        for (int i = 0; i < lists[now].size(); i++) {
            int next = lists[now].get(i);
            if(!isVisited[next]){
                dfs(depth+1, next);
            }
        }

        isVisited[now] = false;
    }

이런 식으로 현 노드에 대해 처리를 해준다면, 시작 정점을 놓칠 일은 없을 것이다.
(이게 싫다면, DFS 함수 들어오기 전에, 시작 노드에 대한 방문처리를 해줘야 한다.)