[백준]13023: ABCDE - JAVA

[백준]13023: ABCDE

www.acmicpc.net/problem/13023

13023번: ABCDE

풀이

모든 경우를 탐색하는 DFS탐색 문제로, A -> B -> C -> D -> E인 관계가 있다면 1을 출력, 아니면 0을 출력하는 문제이다.

위와 같은 연결 관계가 있다면 DFS탐색 깊이가 4가 되는 것을 이용하여 문제를 풀었다.

 

반복문을 사용하여 시작 순서를 돌아가면서 DFS탐색을 하였고, 탐색 깊이가 4가 되는 순간 1을 출력하고 프로그램을 종료했다. 1이 출력되면 그 이후에는 더 이상 탐색하지 않아도 되기 때문이다.

 

모든 DFS탐색 동안 1이 출력이 되지 않는다면 위와 같은 관계를 찾지 못했다는 의미이므로 0을 출력해주었다.

 

코드

import java.util.*;
 
public class Main {    
    
    static int n;
    static ArrayList<Integer>[] list;
    static boolean[] visited;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        int n = scan.nextInt();
        int m = scan.nextInt();
        
        list = new ArrayList[n];
        for(int i = 0; i < n; i++) {
            list[i] = new ArrayList<>();
        }
        
        for(int i = 0; i < m; i++) {
            int a = scan.nextInt();
            int b = scan.nextInt();
            list[a].add(b);
            list[b].add(a);
        }
        
        for(int i = 0; i < n; i++) {
            visited = new boolean[n];
            dfs(i, 0);
        }
        System.out.println(0);
    }
    
    public static void dfs(int x, int len) {
        if(len == 4) {
            System.out.println(1);
            System.exit(0);
        }
        
        visited[x] = true;
        for(int i = 0; i < list[x].size(); i++) {
            int temp = list[x].get(i);
            if(visited[temp] == false) {
                visited[temp] = true;
                dfs(temp, len + 1);
                visited[temp] = false;
            }
        }
    }
}