백준 13023 ABCDE 자바 풀이

한줄 풀이

모든 노드에서 dfs를 한번씩 돌려보면서 깊이가 4 이상인게 있다면 1을 출력해주면 된다.

 

주의점

1. 깊이가 4 이상인것을 찾았을 때 반복문을 빠져나와줘야한다.

그렇지 않으면 시간초과가 난다.

2. 백트래킹을 해줘야한다

재귀 호출문 밑에서 visited를 false로 만들어줘야한다

https://www.acmicpc.net/board/view/34026

글 읽기 - visited[cur] = false; 꼭 들어가야 하는 이유를 알고 싶습니다.

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

public class Main {
    static ArrayList<Integer>[] li;
    static boolean[] visited;
    static int answer = 0;

    public static void main(String[] args) throws IOException {
        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());
        li = new ArrayList[N];
        for (int i = 0; i < N; i++) {
            li[i] = 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());
            li[a].add(b);
            li[b].add(a);
        }
        for (int i = 0; i < N; i++) {
            visited = new boolean[N];
            dfs(i, 0);
            if (answer == 1)
                break;
        }
        System.out.println(answer);
    }

    private static void dfs(int a, int cnt) {
        if (cnt == 4) {
            answer = 1;
            return;
        }
        visited[a] = true;
        for (int b : li[a]) {
            if(visited[b]) continue;
            dfs(b, cnt + 1);
        }
        visited[a] = false;
    }
}