[BOJ] 13023. ABCDE

인접리스트를 활용한 DFS문제이다.

맨처음 문제접근을 BFS로 하였는데, 이 문제에선 5개의 이어진 노드를 찾는 것이여서 DFS를 활용하여 depth가 5가 될때까지를 찾는게 맞는 방향이라 생각해 DFS로 바꾸어 풀었다. 이 문제에서는 주의할 것은 다양한 방법으로 여러갈래로 찾을 수 있기에 visit[i]=false로 다시 바꾸어 주는 작업이 필수적이다. 이것을 해주지 않아 계속 틀렸었다.

예를 들어 위와 같은 그래프가 있고 1번 정점부터 탐색한다고 생각하자. 첫번째 DFS를 실행시킨 결과가 1-2-4-5-3 이라고 생각한다면 depth는 최대 4까지 밖에 찾지를 못한다. 그렇기에 종료조건을 만족하지 못하고, 재귀가 끝나면서 다시 재귀호출을 하게 된다. 1-2 이상황에서 4를 방문했었기네 1-2-3을 해봐야하는데, visit[i]=false가 없다면 3을 가진 정점으로 출발을 하지 못하고, 답이 되는 1-2-3-4-5를 끝내 찾을 수 없게 된다. 이러한 상황때문에 함수 맨끝에 visit[i]=false가 필수적으로 들어가야만 한다.

package online.base;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main_bj_13023_ABCDE {
    
    static int V,E;
    static List<Integer>[] graph;
    static boolean[] visit;
    
    static boolean find;
    
    public static void main(String[] args) throws Exception {
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         StringTokenizer st = new StringTokenizer(br.readLine());
         
         V=Integer.parseInt(st.nextToken());
         E=Integer.parseInt(st.nextToken());
         
         graph=new ArrayList[V];
         for(int i=0;i<V;i++)
             graph[i]=new ArrayList<>();
         
         for(int i=0;i<E;i++) {
             st=new StringTokenizer(br.readLine());
             int v1=Integer.parseInt(st.nextToken());
             int v2=Integer.parseInt(st.nextToken());
         
             graph[v1].add(v2);
             graph[v2].add(v1);
         }
         
         find=false;
         visit=new boolean[V];
         
         for(int i=0;i<V;i++) {
             if(visit[i]==false && find==false)
                 dfs(i,1);
         }
         
         System.out.println(find?1:0);
    }
    
    static void dfs(int i,int depth) {
//        System.out.println(i+", depth"+depth);
        if(depth==5) {
            find=true;
            return;
        }
        visit[i]=true;
        
        for(int next : graph[i]) {
            if(visit[next]==false) {
                dfs(next,depth+1);
            }
        }
        visit[i]=false;
            
    }
    
}