[백준] 13023 ABCDE - DFS

문제 링크 : https://www.acmicpc.net/problem/13023

🍊해결방법

• N개에 상관없이 A B C D E 이렇게 5명의 친구 만족하면 된다
• 방문배열을 사용할 때 FALSE 처리를 해야 모든 경우의 수를 확인 가능

😀풀이

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

public class Main {

    static int N;
    static int M;
    static List<Integer>[] list;
    static boolean[] visit;
    static int flag;

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // A B C D E 존재하면 되므로 N개의 개수 상관없이 친구관계 5명 찾기 가능하면 1

        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        list = new ArrayList[N];

        for(int i=0; i<N; i++){
            list[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());

            list[a].add(b);
            list[b].add(a);
        }

        visit = new boolean[N];

        flag = 0;

        for(int i=0; i<N; i++){
            if (flag == 1) continue;

            dfs(i, 1);
        }

        System.out.println(flag);

    }// end main


    static void dfs(int idx, int cnt){

        if (cnt == 5){

            flag = 1;

            return;
        }

        visit[idx] = true;

        for(int nx : list[idx]){
            if (!visit[nx]){
                dfs(nx, cnt+1);
            }
        }

        visit[idx] = false;
    }

}