[백준 - 13023] ABCDE .java

https://www.acmicpc.net/problem/13023

 

 

Solution

DFS를 재귀함수와 백트래킹을 이용해서 깊이가 5이면 1을 출력하면 되고, 

5의 깊이를 찾을 때까지 모든 노드를 탐색한다. 하지만 노드의 수와 간선의 수가 적어서 DFS로 충분히 가능하다.

 

 

백트래킹(Backtracking)

• 문제를 해결하는 과정에서 부분적인 해결책을 찾으면서 탐색을 수행하고, 
• 만약 현재 경로가 더 이상 유효하지 않거나 최적의 해결책이 아닐 경우, 이전 상태로 되돌아가서 다른 경로를 탐색하는 기법

-> 깊이 우선 탐색(DFS)와 결합하여 많은 경우 문제를 효과적으로 해결

 

 

재귀 탐색에서의 백트래킹

1. 현재 노드 방문 상태 초기화:
   • DFS 탐색 중, 현재 노드에서 다른 노드로 탐색을 진행하면서 깊이 5에 도달 가능함.
   • 깊이 5에 도달하면, 현재 경로를 기록하고 arrive 변수를 true로 설정하여 깊이 5인 경로를 찾았음을 저장
   • 그 후, 다른 경로를 탐색하기 위해 현재 노드의 방문 상태를 초기화해야함
2. 백트래킹의 필요성:
   • DFS는 재귀적으로 호출되기 때문에, 현재 노드에서 다른 노드로 탐색을 진행하면서 그 경로를 다 탐색한 후에는 다시 원래 상태로 돌아가야함
   • 따라서, 현재 노드에서 모든 가능한 경로를 탐색한 후에는 해당 노드를 방문하지 않은 상태로 되돌려야 한다.
     
     => DFS 함수 마지막에 방문 초기화
3. arrive 변수를 사용하는 이유:
   • arrive 변수는 깊이 5인 경로를 찾았는지 여부를 기록
   • 깊이 5에 도달한 상태에서는 더 이상 탐색할 필요가 없으므로, arrive 변수를 true로 설정하고 탐색을 종료
   • DFS 탐색 중에 이미 깊이 5인 경로를 찾았음을 확인하고, 추가적인 불필요한 탐색을 방지 가능

 

arrive 변수의 사용과 현재 방문한 노드의 방문 초기화가 핵심이다.

나머지 부분은 전에 풀었던 DFS 풀이와 유사하다.

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static boolean[] visited; // 노드 방문 상태를 저장하는 배열
    static ArrayList<Integer>[] nums; // 각 노드의 인접 노드 리스트를 저장하는 배열
    static boolean arrive; // 깊이가 5인 경로를 찾았는지 여부를 저장하는 변수

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 노드 개수와 에지 개수 입력
        int n = sc.nextInt(); 
        int m = sc.nextInt(); 

        // 초기화
        arrive = false; // 깊이가 5인 경로를 아직 찾지 못함
        visited = new boolean[n]; // 모든 노드 방문 상태를 false로 초기화
        nums = new ArrayList[n]; // 각 노드의 인접 노드 리스트 초기화

        // 인접 리스트 초기화
        for (int i = 0; i < n; i++) {
            nums[i] = new ArrayList<>(); // 각 노드에 대해 빈 리스트 생성
        }

        // 인접 리스트에 에지 정보를 저장
        for (int i = 0; i < m; i++) {
            int s = sc.nextInt(); 
            int e = sc.nextInt();
            // 무방향 그래프이므로 양쪽 모두에 추가
            nums[e].add(s);
            nums[s].add(e); 
        }

        // 모든 노드에서 DFS 탐색 시작
        for (int i = 0; i < n; i++) {
            DFS(i, 1); // 노드 i에서 깊이 1로 시작

            // 깊이가 5인 경로를 찾았으면 탐색 중지
            if (arrive) break;
        }

        // 결과 출력
        if (arrive) System.out.println("1"); // 깊이 5의 경로가 존재하면 1 출력
        else System.out.println("0"); // 깊이 5의 경로가 없으면 0 출력
    }

    static void DFS(int now, int depth) {
        // 현재 깊이가 5이거나 깊이 5인 경로를 이미 찾았을 경우
        if (depth == 5 || arrive) {
            arrive = true; // 깊이 5의 경로를 찾았음
            return; // 재귀 호출 종료
        }

        visited[now] = true; // 현재 노드 방문 처리

        // 현재 노드와 연결된 모든 노드에 대해 DFS 수행
        for (int i : nums[now]) {
            if (!visited[i]) { // 방문하지 않은 노드에 대해
                DFS(i, depth + 1); // 깊이를 하나 증가시켜서 DFS 호출
            }
        }

        // 백트래킹: 현재 노드의 방문 상태를 초기화
        visited[now] = false;
    }
}