백트래킹 개요

모든 경우의 수를 탐색해서(보통 재귀함수, 또는 DFS로 구현) 답인지 확인하는 방법을 브루트포스라고 한다. 그러나 입력 크기가 커지면 브루트포스의 성능은 매우 안좋다.
따라서 모든 탐색을 하는중, 이미 정답과 모순이 되는 경우일 때 더이상 탐색하지 않고 가지치기(pruning) 를 하여 상위 노드로 가는 것을 백트래킹이라 한다.
일반적으로 $O(20!)$까지는 브루트포스로 감당할 수 있다.
입력 크기 $n$이 20 이하일 경우 고려해볼 수 있다

[BOJ 9663] N-Queen

백트래킹의 예제격인 문제이다. (개인적으로 예제치고 어렵다고 생각한다. 백준에서도 골드5이다.) 그렇지만 이 문제만큼 백트래킹을 제대로 표현하기 쉽지 않다. 체스판의 퀸은 사방팔방으로 공격이 가능하다. 이때 NxN 체스판에 N개의 퀸을 몇개 놓을 수 있는지 묻는 문제이다.

브루트포스 방법

우선 체스판에 차례대로 퀸을 놓으면서 가능하면 count를 증가시키면 된다. 당장 첫번째 퀸을 놓는 경우의 수만 $n^2$이고, 두번째 퀸을 놓는 경우의 수는 1개 줄어든 $n^2-1$

백트래킹 방법

우선 퀸의 공격의 특징을 최대한 이해해보자. (1, 1)에 퀸을 놓으면 (1, 2), (1, 3), ... (1, N)에는 더이상 퀸을 놓을 수 없다. 이렇게 가로 공격방향만 고려해도 (세로, 대각선을 고려하지 않아도) 한 줄에는 퀸을 1개만 놓을 수 있다는 것을 알 수 있다. 즉 (NxN)에서 놓을 수 있는 퀸의 개수는 N개이다.
이제 2번째 줄(row)에 퀸을 놓아보자. (1, 1)에 퀸이 있으므로 (2, 1), (2, 2)에는 퀸을 놓을 수 없다. 그러므로 2번째 퀸을 (2, 1), (2, 2)에 놓는 경우는 더 이상 탐색할 이유가 없다. 그리고 (2, 3), (2, 4)에 놓는 경우는 가능하다. 이렇게 탐색이 가능한 경우를 유망하다(promising) 라고 한다. 유망한 경우에만 탐색을 깊이 가면 된다.
2번째 퀸을 (2, 3)에 놓은 경우(b), 3번째 퀸을 놓을 수 없다.(c) 역시 유망하지 않으므로 더이상 탐색하지 않고 상위 노드(2, 3) -> (1, 1)로 간다. 그리고 다시 2번째 퀸을 (2, 4)에 놓는 경우부터 탐색하는 것이다.(d)
브루트포스의 경우보다 확연히 줄어든 것을 알 수 있다.

코드로 표현하기

• 유망한 경우를 코드로 어떻게 표현할 것 인가?
  가로, 세로 방향으로 공격받는 것은 같은 row인지만 확인하면 된다. (같은 col에는 놓지 않음을 이전에 설명했다.)
  (6, 4)에 있는 퀸은 (3, 1), (2, 8)에 있는 2개의 퀸에게 공격을 받는 위치에 있다. 퀸이 공격받는다는 것을 좌표로 어떻게 알 수 있을까?
  
  $col(x)$를 $x$번째 row에 있는 column의 번호라고 하자. (한개의 row에는 한개의 퀸만 놓일것임을 이전에 설명했다.) 위 그림의 경우 $col(2) = 8$

  공격받는 퀸의 위치
  $col(x) = col(y)$

• 정답 코드

#include <stdio.h>
#include <cmath>

int N; // the number of Queens
int col[15]; // col[x] : find column of Queen where row is x
int ans = 0;

int promising(int row) {
	// check if any queen threaten queen in the i_th row
    
	for (int i = 1; i < row; i++) {
		// queen is threaten by same row or column
		if (col[i] == col[row]) {
			return 0;
		}
		
		// queen is threaten by diagonal queen
		if (abs(col[i] - col[row]) == abs(i - row)) {
			return 0;
		}
	}

	// the queen is not threaten by any queens
	return 1;
}

void nQueens(int row) {
/*  Based on DFS(recursive) Algorithm
    int row : the current row of Queen
*/
	// all queens are on the board without threat
	if (row == N) {
		ans++;
	}
	else {
		for (int i = 1; i <= N; i++) {
			col[row + 1] = i;
			if (promising(row + 1)) {
				nQueens(row + 1);
			}
			else {
				col[row + 1] = 0;
			}
		}
	}

	col[row] = 0; // backtracking, clear visit

}

int main() {
	scanf("%d", &N);

	// test N columns
	for (int i = 1; i <= N; i++) {
		col[1] = i; 
		nQueens(1); // start from 1st row
	}
	
	printf("%d", ans);
	return 0;
}

[BOJ] 1182 부분수열의 합

1개를 선택하는 경우, 2개를 선택하는 경우, ..., N개를 선택하는 경우 모두 고려해야한다. 백준의 N과M시리즈 를 공부한 후에 오면 조합의 수를 어떻게 선택하는지 알 수 있다.

# python code
N, S = map(int, input().split())
L = list(map(int, input().split()))

# 정답의 개수
count = 0

def dfs(start, size, pick_size, pick_list = []):
    """ start: 배열의 시작 인덱스
        size : 현재까지 pick한 개수
        pick_size : 전체 pick해야 하는 개수
        pick_list : 현재까지 pick한 배열
    """
    
    # 목표 개수만큼 pick했으면 합계를 구한다
    if size == pick_size:
        total = sum(pick_list)
        
        # 합계가 S과 같다면 정답 개수 증가
        if total == S:
            global count
            count += 1
            #print(pick_list)
        return

    # 아직 다 pick하지 않았으면 이어서 pick한다.
    for i in range(start, N):
        pick_list.append(L[i])  # L[i]를 pick한다.
        dfs(i + 1, size + 1, pick_size, pick_list)
        pick_list.pop()  # L[i]를 pick에서 제외한다
    return

for i in range(1, N + 1):
    dfs(0, 0, i)
print(count)