[BAEKJOON] - 13023번 : ABCDE

13023번 문제 링크

⌛ 시간 복잡도

• 2초 : 2억
• 제한 조건 : 최대 2,000
• O(n^2) 이하 사용 가능
• dfs -> O(V+E) = 4,000
• 모든 노드를 도는 경우, 4,000 * 2,000 = 8,000,000 이므로 dfs 사용 가능

📜 로직

해당 문제는 연결 노드 중 5개의 연결 노드가 존재하는 경우 "1"을 출력, 아닌 경우 "0"을 출력하는 알고리즘을 구현하면 됩니다.
1. N개의 노드 수만큼 loop를 생성하여 dfs를 호출합니다.
2. 연결된 노드(depth)가 5개인 경우, 1을 출력하고 dfs를 끝냅니다.
3. 방문 배열에 해당 노드의 방문 표시를 해줍니다.
4. 노드의 연결 노드들을 확인하여 방문한 노드가 아닌 경우 인접 노드로 depth에 1을 더해준 뒤, dfs를 재귀호출해줍니다.

☢️ 주의할점

• dfs 로직 내 arrive 로 early return을 한 이유는 한 분기에서 depth == 5를 충족한 경우, 다른 분기는 탐색할 필요가 없기 떄문입니다.

ex)

• 3 - 4,5
• 1 → 2 → 3 → 4 → 6 인 경우, arrive가 true가 됩니다.
• 이 때, 1 → 2 → 3 → 5 분기는 확인할 필요가 없기 때문에, early return을 해줍니다.

😀 성공

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

public class Main{
    static ArrayList<Integer>[] arr;
    static boolean[] visited;
    static boolean arrive;
    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());
        arr = new ArrayList[N];
        visited = new boolean[N];
        
        for(int i=0; i < N; i++){
            arr[i] = new ArrayList<Integer>();
        }
        
        for(int i=0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            arr[a].add(b);
            arr[b].add(a);
        }
        
        for(int i=0; i < N; i++){
            dfs(i,1);
        }
        
        if(arrive)
            System.out.println(1);
        else
            System.out.println(0);
        br.close();
    }
    
    static void dfs(int now, int depth){
        if(arrive){
            return;
        }
        
        if(depth == 5){
            arrive = true;
            return;
        }
        
        visited[now] = true;
        
        for(int i : arr[now]){
            if(!visited[i])
                dfs(i,depth+1);
        }
        
        // false 초기화 해주는 이유 : 백트래킹(back-tracking) 과정에서 사용.
        // 모든 경로를 탐색한 뒤에 해결책을 찾지 못한 경우, 이전으로 돌아가야 합니다.
        // 이 때, visited[now] = false 를 통해 현재 노드의 방문 상태를 초기화.
        // 이 과정을 통해 다음 탐색 시, 다른 경로 탐색 시 현재 노드를 다시 방문할
        // 수 있습니다.
        visited[now] = false; 
    }
}