[백준] 13023번 : ABCDE

13023번: ABCDE

---

[DFS]

0번부터 N-1번을 시작 정점으로 총 N번의 DFS를 실시하는데, 각 DFS가 끝나면 해당 정점의 visit[current] = false로 다시 변경한다. 이는 백트래킹 문제에서 주로 쓰던 방법이다. 해당 아이디어의 출처는 다음 링크에 있다.

www.acmicpc.net/board/view/34026

 

그리고 DFS를 한층 한층 진행할 때마다 depth를 증가시키며, depth가 5가 되면 결과 flag를 true로 변경하고 루프의 진행을 멈춘다.

 

# Code </>

public class Main {

    static List<Integer>[] list = new ArrayList[2000];
    static boolean[] visit;
    static boolean flag = false;

    static void DFS(int start, int depth){

        visit[start] = true;
        depth++;

        if(depth == 5){
            flag = true;
            return;
        }

        for(int next : list[start])
            if(!visit[next])
                DFS(next, depth);

        visit[start] = false;
        depth--;
    }

    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());

        for(int i=0; i<n; i++) list[i] = new ArrayList<>();

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());

            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            list[v1].add(v2);
            list[v2].add(v1);
        }

        for(int i=0; i<n; i++){
            visit = new boolean[2000];
            if(flag) break;
            DFS(i, 0);
        }
        if (flag) System.out.println(1);
        else System.out.println(0);
    }
}