[문제풀이기법] 백 트래킹 (Backtracking)

1. 백트래킹이란 ?

알고리즘이 아닌 문제풀이 기법이다.

• 해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다면 바로 백트래킹하여 다른 후보군으로 넘어가 최적의 해를 찾는 방법이다.
• 실제 구현 시에는 고려할 수 있는 모든 경우의 수를 상태공간트리를 통해 표현한다.
  • 각 경우의 수는 DFS방식으로 확인할 수 있다.
  • 상태 공간 트리를 탐색하면서 조건이 맞지 않으면 해의 후보가 될만한 곳으로 넘어가서 탐색한다.
    • Promising : 해당 루트가 조건에 맞는지 검사하는 기법
    • Pruning(가지치기) : 조건에 맞지 않으면 포기하고 다른 루트로 가서 탐색하여 시간을 줄이는 기법

백트래킹은 트리 구조를 기반으로 DFS탐색을 진행하면서 각 루트에 대해 조건이 맞는지 체크하고 만약 조건이 맞지 않으면 더이상 DFS하지 않고 Pruning한다.

상태공간트리

• 문제 해결 과정의 상태를 노드로 나타낸 트리

 

2. 백트래킹 대표 문제 - N Queen 문제

• NxN 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제이다.
• 퀸은 다음과 같이 이동할 수 있으므로, 배치된 퀸은 서로 공격할 수 없는 위치에 배치해야한다.

Pruning(조건에 맞지 않으면 포기) - N Queen 

• 한 행에는 하나의 퀸만 위치할 수 있다. 
• 첫번째 행부터 퀸을 위치하고, 다음 행에 첫번 째 행의 퀸이 이동할 수 없는 위치를 찾아 퀸을 배치한다.
• 만약 앞 행의 퀸으로 인해 배치할 수 있는 위치가 없는 경우는 이전 행의 퀸 위치를 바꾼다.
  • 즉, 맨 위의 행부터 전체 행까지 퀸의 배치가 가능한 경우의 수를 상태공간 트리 형태로 만든 후,각 경우를 맨위의 행부터 DFS 방식으로 접근하고 해당 경우가 진행할 수 없을 경우, 진행하지 않고 다른 경우를 체크한다. 

Promising(조건에 맞는지 검사) - N Queen 

• 해당 루트가 조건에 맞는지 검사하는 기법을 사용하여, 현재까지 앞선 행에서 배치한 퀸이 이동할 수 없는 위치가 있는지를 확인한다.
  • 한 행에 하나의 퀸만 배치가 가능하므로 수평체크는 필요없음.

• 수직 체크 : (하나의 행은 1개의 퀸이므로 x는 생각안함) | ( 현재위치의 y값 == 배치된 퀸의 y값 )
  • 수직이라면 해당 위치는 조건에 맞지 않는다.
• 대각선 체크 : ( | 현재위치의 x값 - 배치된 퀸의 x값 | == | 현재위치의 y값 - 배치된 퀸의 y값 | )
  • 양쪽이 같다면 해당 위치는 조건에 맞지 않는다.

 

3. N Queen 문제 코드

public class Backtracking_NQueen {	
	public static void main(String[] args) {
		int N = 5;
		int candidate[] = new int[N];
		DFS(N, 0, candidate);
	}
	
	// DFS(N, 현재 행, 현재 선택된 퀸 후보자)
	public static void DFS(int N, int current_row, int[] current_candidate) {
		if (current_row == N) { //N개의 퀸을 배치했다면 결과 출력
			for (int q : current_candidate) {
				System.out.print(q + " ");
			}
			System.out.println();
			return;
		}
		
		//퀸 배치
		for (int i = 0; i < N; i++) {
			if (is_available(current_candidate, current_row, i)) {
				current_candidate[current_row] = i;
				DFS(N, current_row + 1, current_candidate);
			}
		}
	}
	
	//퀸 배치 조건 확인
	public static boolean is_available(int[] candidate, int current_row, int current_col) {
		for (int i = 0; i < current_row; i++) {
			if (candidate[i] == current_col 
					|| Math.abs(candidate[i] - current_col) == Math.abs(current_row - i)) {
				//각 행의 퀸들의 y값과 같거나 || | 각 행의 퀸의 y값 - 현재 y위치 | == | 현재 x위치 - 각 행의 퀸 x값 |  
				return false;
			}
		}
		return true;
	}
}