깊이 우선 탐색(Depth-First-Search)

DFS(깊이 우선 탐색)의 정의

DFS(Depth-First Search)는 그래프나 트리를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 깊이 들어가며 탐색하는 알고리즘이다.
스택(Stack) 자료구조를 사용하거나 재귀 호출을 통해 구현되며, 한 노드에서 다음 노드로 갈 수 있는 만큼 깊이 들어간 후 더 이상 갈 수 없을 때 다시 되돌아오는 방식이다.

---

DFS를 사용하는 경우

1. 모든 경로를 탐색해야 하는 경우
   ex: 미로에서 출구까지 갈 수 있는 모든 경로 찾기, 백트래킹 문제

2. 그래프에서 연결 요소를 찾을 때
   ex: 연결된 노드 집합 찾기, 그룹의 개수 세기

3. 조합, 순열을 구하는 문제
   ex: N개의 숫자 중에서 M개를 뽑는 경우의 수 구하기 (백트래킹 기반 DFS)

4. 트리 구조를 탐색할 때
   ex: 이진 트리의 전위(pre-order), 중위(in-order), 후위(post-order) 순회

---

DFS의 장점과 단점

• DFS의 장점

1. 간단한 구현
   재귀를 사용하여 직관적이고 간단하게 구현할 수 있다.

2. 효율적인 메모리
   BFS처럼 모든 노드를 큐에 저장하지 않기 때문에, 메모리 사용량이 적다.

3. (운이 좋다면)해를 빠르게 찾을 수 있음
   정답이 깊은 곳에 있는 경우 BFS보다 더 빠르게 도달할 수 있다.

• DFS의 단점

1. 최단 경로를 보장하지 않음
   경로를 깊이 먼저 탐색하기 때문에 목적지까지 도달하는 가장 짧은 경로를 보장하지 않는다.

2. 스택 오버플로우 위험
   재귀 호출이 너무 깊어지면 스택 오버플로우가 발생할 수 있다.

3. 불필요한 경로를 탐색할 수 있음
   해가 없는 경로도 끝까지 탐색하기 때문에 시간이 오래 걸릴 수 있다.

---

DFS를 활용한 백트래킹 문제 해결

DFS를 활용한 예시 코드를 찾던 중 DFS를 이용해 백트래킹 문제를 해결한 백준 예시 코드를 찾았다.

백준 9663번 - N-Queen 문제

문제의 핵심은 N x N 체스판 위에 N개의 퀸을 서로 공격하지 않도록 놓을 수 있는 경우의 수를 구하는 것이다.
한 행마다 퀸을 하나씩 배치하면서 조건을 만족하지 않으면 이전 상태로 되돌아가는 백트래킹(DFS)을 사용한다.

public class NQueen {
    static int N;
    static int count = 0;
    static int[] board;

    public static void main(String[] args) {
        N = 8; // 원하는 N값 설정
        board = new int[N];
        dfs(0);
        System.out.println("경우의 수: " + count);
    }

	// 각 행마다 가능한 열에 퀸을 놓아보며 가능한 경우에만 다음 행으로 넘어간다.
    static void dfs(int depth) {
        if (depth == N) {
            count++;
            return;
        }

        for (int i = 0; i < N; i++) {
            board[depth] = i;

            if (isValid(depth)) {
                dfs(depth + 1);
            }
        }
    }

	// 퀸이 서로 공격하지 않는 조건을 검사한다.
    static boolean isValid(int row) {
        for (int i = 0; i < row; i++) {
            if (board[row] == board[i] || Math.abs(row - i) == Math.abs(board[row] - board[i])) {
                return false;
            }
        }
        return true;
    }
}