03. 깊이 우선 탐색(DFS)

1. 알고리즘 정의

Depth-First Search

한 방향으로 최대한 깊게 탐색한 뒤, 더 이상 갈 곳이 없으면 백트래킹하면서 다른 경로를 탐색하는 알고리즘이야.

 

[구조]

A
├── B
│   └── D
└── C

BFS 탐색 순서 (시작: A)
→ A → B → D (재귀:백트래킹) → C

 

2. 알고리즘 구현

1) 재귀함수 활용

void dfs(int node, boolean[] visited) {
    visited[node] = true;
    System.out.print(node + " ");
    
    for (int next : graph[node]) {
        if (!visited[next]) {
            dfs(next, visited);
        }
    }
}

 

2) Stack 활용

void dfsStack(int start) {
    Stack<Integer> stack = new Stack<>();
    boolean[] visited = new boolean[n + 1];

    stack.push(start);

    while (!stack.isEmpty()) {
        int node = stack.pop();

        if (!visited[node]) {
            visited[node] = true;
            System.out.print(node + " ");

            for (int next : graph[node]) {
                if (!visited[next]) {
                    stack.push(next);
                }
            }
        }
    }
}

 

3. 활용 예시

🔍 미로 탐색	출구까지 가능한 경로 찾기
🧩 백트래킹	N-Queen, 스도쿠, 조합/순열 생성
🧱 연결 요소 탐색	그래프에서 서로 연결된 그룹 찾기
🕳️ 사이클 감지	순환 구조 있는지 검사
🌲 트리 탐색	후위순회(postorder) 등
🌐 웹 크롤링	링크 따라가며 깊게 탐색
🎮 게임 맵 탐색	DFS로 갈 수 있는 경로 탐색