[알고리즘] 백트래킹 (Backtracking)

1. 백트래킹 (Backtracking) 이란 무엇일까

---

현재 상태에서 다음 상태로 가는 모든 경우의 수를 찾아서 이 모든 경우의 수가 더 이상 유망하지 않다고 판단되면 이전의 상태로 돌아가는 것을 말한다. 즉, 모든 경우의 수를 탐색하며 최적해를 구하는 과정에서 유망하지 않은 쪽은 더 이상 구하지 않는 것이다. 이때, 모든 경우의 수를 다 탐색하는 것은 부르트포스라고 한다. 

 

(1) 용어 정리

• 유망 (Promising) : 해가 될 가능성이 있는 경우 유망하다고 한다.
• 가지치기 (Pruning) : 해가 될 가능성이 없는 경우 해당 노드를 제외하는 것을 말한다.
• 백트래킹 (Backtracking) : 유망하지 않은 쪽으로 가지 않고 되돌아 오는 것을 말한다.

 

 

 

---

 

 

 

2. 백트래킹 (Backtracking) 예시

---

(1) N-Queen 문제

- N x N 체스판에서 퀸 N개를 서로 공격할 수 없도록 배치하는 경우의 수

 

 

배열 설정

우선 n개의 배열을 하나 생성한다.

이 배열은 행들을 의미하고 배열안에 있는 값은 열을 의미한다.

예를 들어 아래의 그림과 같다.

 

static int[] board = new int[n];

 

 

 

for 문을 이용하여 DFS 설정하기

isPromising 이라는 함수를 만들어 해당 위치에 퀸이 위치하여도 되는지 확인한다.

만약 해당 함수에서 true가 반환된다면, 위치가 적합하다는 의미이므로 다음 행으로 이동하기 위해 depth +1 을 하여 다음 행으로 이동한다.

 

for(int i = 0; i<n; i++) {
	board[row] = i;
    
    if(isPromising(row)) {
    	nQueen(row + 1);
    }
}

 

 

 

해당 위치에 퀸이 존재해도 되는지 확인하는 isPromising 메서드

퀸이 같은 열에 위치하지 않고 대각선으로도 위치하지 않을 때 true를 반환한다.

즉, 선언한 배열에서 같은 값이 존재하거나 대각선 위치에 존재한다면 false를 반환한다.

public static boolean isPromising(int row) {
	for (int i =0; i < row; i++) {
    	if (board[row] == board[i]) {
        // 퀸이 같은 열에 위치할 때
        	return false;
        } else if (row - i == Math.abs(board[row] - board[i]) {
        // 현재 퀸의 위치의 대각선에 이미 퀸이 존재할 때
        	return false;
        } else {
        	return true;
        }
    }
}

 

 

 

재귀함수 탈출 조건

배열의 크기가 주어진 N과 같으면 탈출한다.

if(row == n) {
	return;
}