okayoki

모든 경우의 수를 검사하되, 특정 조건에 맞을 때만 검사하는 방식!

백트래킹 문제는 보통 DFS알고리즘에 조건을 검사하는 부분을 추가하여 해결한다.

대표적인 문제로 N-Queen이 있다.

N-Queen

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

퀸은 가로, 세로, 대각선 방향으로 움직일 수 있는 체스의 말이다.

모든 경우의 수를 따진다면 (각 행마다 퀸을 놓을 수 있는 방법의 수) N x (행의 개수) N 으로 O(N^N)의 시간 복잡도를 가진다.

조건 검사 없이 모든 경우의 수를 따진다면 체스판의 크기가 조금만 커져도 해답을 찾는데 시간이 오래 걸릴테지만,

백트래킹으로 조건을 검사하면서 해당 조건이 만족될 때만 퀸을 놓고, 그 다음 퀸을 놓을 자리를 찾는다면 시간을 단축할 수 있다.

// 재귀적으로 함수를 호출하여 행 0~n-1까지 체크한다.
void findQueen(int n){
	if( n>=N ) count++;
	  
	for(int i=0; i<N; i++){		
        	// (n, i)에 퀸을 배치할수있는지 체크
		if( arr[i]==true ) continue;
		if( dup[n+i] == true || ddown[N-1+n-i]==true ) continue;
        	// (n,i)에 퀸을 놓고
		arr[i] = dup[n+i] = ddown[N-1+n-i] = true;
		findQueen(n+1);			// 다음 행에서 퀸을 놓을 자리를 재귀적으로 찾는다.
		// (n,i)에서 퀸을 제거하고 n번째 행에서 다른자리에 퀸을 또 놓을 수 있는지 체크할것임
        arr[i] = dup[n+i] = ddown[N-1+n-i] = false;
	}
}

백트래킹에서 중요한 것!

재귀를 타고 들어가기 전에 방문했던(작업했던) 것을 재귀에서 빠져나왔을 때 원래대로 돌리는 작업을 통해서 해당 작업(방문)을 이후에 다시 할 수 있도록 하는 것.