[백준 13023] ABCDE (Java)

🚀 문제 분석

• 목표: $N$명의 사람 중 $A-B-C-D-E$와 같이 5명이 일직선으로 연결된 관계가 존재하는지 확인합니다.
• 핵심: 그래프 상에서 길이가 4인 경로(에지 4개, 정점 5개)가 존재하는지 찾는 것이 포인트입니다.
• 제약: 정점 $N \le 2,000$, 간선 $M \le 2,000$. 모든 정점에서 DFS를 시작해도 시간 내에 충분히 가능합니다.

💡 해결 전략: 깊이(Depth) 중심의 탐색

단순히 연결된 덩어리를 찾는 게 아니라, "얼마나 깊게 들어갈 수 있는가"가 중요합니다.

1. 인접 리스트: 간선 정보를 저장하기 위해 ArrayList[]를 사용합니다.
2. 모든 정점 탐색: 어느 정점이 경로의 시작점(A)이 될지 모르므로 모든 정점에서 DFS를 시작합니다.
3. 백트래킹(Backtracking): 한 경로를 탐색한 후, 다른 경로도 확인해야 하므로 방문 표시를 다시 false로 되돌려야 합니다.
4. 조기 종료: depth == 4에 도달하는 즉시 탐색을 멈추고 1을 출력합니다.

💻 구현 코드 (Java)

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

public class Main {
    static List<Integer>[] adjList;
    static boolean[] visited;

    public static void main(String[] args) throws Exception {
        // ... (입력 로직 생략)

        // 모든 노드에서 DFS 시작
        for (int i = 0; i < n; i++) {
            if (dfs(i, 0)) {
                System.out.println(1);
                return;
            }
        }
        System.out.println(0);
    }

    static boolean dfs(int node, int depth) {
        // 깊이가 4(에지 4개)면 5명이 연결된 것
        if (depth == 4) return true;

        visited[node] = true; // 방문 처리
        for (int next : adjList[node]) {
            if (!visited[next]) {
                if (dfs(next, depth + 1)) return true;
            }
        }
        visited[node] = false; // 백트래킹: 다른 경로 탐색을 위해 방문 해제
        return false;
    }
}

🧐 기술적 고찰

• 백트래킹의 필수성: 일반적인 DFS(연결 요소 찾기)와 달리, 이 문제는 경로를 찾는 것이므로 특정 노드를 거쳐가는 모든 경우의 수를 고려해야 합니다. 따라서 리턴 시 방문 배열을 원복하는 과정이 반드시 필요합니다.
• 시간 복잡도: 최악의 경우 $O(N \times M)$ 근처까지 갈 수 있지만, 문제의 제약 조건이 작고 depth == 4에서 조기 종료되므로 효율적으로 동작합니다.
• 인접 행렬 vs 리스트: $N=2,000$이므로 인접 행렬($N^2 = 4,000,000$)도 가능하지만, 탐색 효율을 위해 인접 리스트를 사용하는 것이 더 권장되는 패턴입니다.