[필독!!] -> DFS, 백트랙킹, 조합, 순열

📊 DFS, 백트랙킹, 조합, 순열

유형	시간 복잡도	안전한 N의 한계선	핵심 특징
1차원 단방향 DFS	$O(2^N)$	$N \le 20 \sim 25$	오직 오른쪽으로만 전진 (싸이클 없음). 방문 해제가 필요 없음.
2차원 상하좌우 DFS	$O(4^{row \times col})$ (최악)	$row,col \le 4 \sim 5$	상하좌우 모든 경로를 탐색하며 방문 배열을 원상복구함.
조합 (Combination)	$O(2^N)$ 또는 $O(\binom{N}{R})$	$N \le 20$	순서를 고려하지 않음. start 인덱스로 뒤쪽만 탐색.
순열 (Permutation)	$O(N!)$	$N \le 10 \sim 11$	순서를 고려함. 항상 처음부터 검사하며 visited 사용.

잠깐!! 여기서 2차원 상하좌우 DFS의 경우

row, col == 5 일때

$4^{25}$ 라고 생각하여 무조건 시간초과 아니냐라고 궁금해 할 수 있지만

visited, 목표점 도달시 조기종료를 통해 대략 실제 연산량은 다음과 같다고 한다.

$1.5 \times 10^{25}$

1. 1차원 단방향 DFS

static void dfs1D(int idx, int currentSum){
    if(idx==N){
        if(currentSum==target) found=true;
        return;
    }
    dfs1D(idx+1,currentSum+arr[idx]);
    dfs1D(idx+1,currentSum);
}

2. 2차원 상하좌우 DFS

static void dfs2D(int r,int c,boolean[][] visited){
    if(r==targetR&&c==targetC){
        pathCount++;
        return;
    }
    for(int d=0;d<4;d++){
        int nr=r+dr[d], nc=c+dc[d];
        if(nr>=0&&nr<row&&nc>=0&&nc<col&&!visited[nr][nc]){
            visited[nr][nc]=true;
            dfs2D(nr,nc,visited);
            visited[nr][nc]=false;
        }
    }
}

3. 조합

static void combination(int start,int depth){
    if(depth==R) return;
    for(int i=start;i<N;i++){
        combination(i+1,depth+1);
    }
}

4. 순열

static void permutation(int depth,boolean[] visited){
    if(depth==R) return;
    for(int i=0;i<N;i++){
        if(!visited[i]){
            visited[i]=true;
            permutation(depth+1,visited);
            visited[i]=false;
        }
    }
}