[JAVA] 백준 13023 깊이 우선 탐색 (DFS)

 

 

 

 

 

13023번: ABCDE

문제

A → B → C → D → E 이렇게 관계가 그려지도록 이어지는 그래프가 존재한다면 1을 출력하라는 문제이다.

이렇게 되기 위해서는 DFS를 통해서 깊이가 5가 되는 경우를 출력하면 된다.

풀이

DFS를 수행하면서 depth가 5가 된다면 DFS를 종료하고 출력하면 된다.

flag를 하나 두고 depth가 5라면 flag를 true로 전환해 DFS를 종료한다.

만약 현재의 DFS가 찾지 못하고 종료된다면 현재 값은 방문하지 않은 것으로 하고 종료한다.

 private static void DFS(int num, int depth){
        if(flag || depth == 5) {
            flag = true;
            return;
        }

        V[num] = true;
        for (int x : A[num]){
          if(!V[x]){
              DFS(x, depth+1);
          }
        }
        V[num] = false;
    }

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

class Main {

    public static ArrayList<Integer>[] A;
    public static boolean V[];
    public static boolean flag = false;
    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 e = Integer.parseInt(st.nextToken());
        A = new ArrayList[N];
        V = new boolean[N];
        for(int i=0; i<N; i++){
            A[i] = new ArrayList<>();
        }

        for(int i = 0; i<e; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            A[x].add(y);
            A[y].add(x);
        }

        for(int i=0; i<N; i++){
            DFS(i, 1);
            if(flag) break;
        }
        if(flag) System.out.println("1");
        else System.out.println("0");
    }

    private static void DFS(int num, int depth){
        if(flag || depth == 5) {
            flag = true;
            return;
        }

        V[num] = true;
        for (int x : A[num]){
          if(!V[x]){
              DFS(x, depth+1);
          }
        }
        V[num] = false;
    }
}

결과