[Algorithm] 백트래킹 (Backtracking)

1. 백트래킹이란?

백트래킹은 모든 조합의 수(완전 탐색)를 조건이 만족할 때(유망할 때)만 살펴보는 것이다.

• Backtracking은 임의의 집합(set)에서 주어진 기준(criterion)대로 원소의 순서(sequence)를 선택하는 문제를 푸는 데 사용한다. 

 

2. DFS VS Backtracking

(1) DFS

• DFS는 가능한 모든 경로를 탐색한다.
• 불필요한 것 같은 (유망하지 않은) 경로도 탐색하기 때문에 경우의 수를 줄이지 못한다.

(2) Backtracking (DFS + 조건)

• DFS를 통해 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아간다.
• 백트레킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것이다.
• DFS 등으로 모든 경우의 수를 탐색하는 과정에서 조건문을 이용해서 유망한 지 판단한다.

 

3. Backtracking의 유망성(Promising) 판단

(1) 유망하다(promising)

• 해가 될 가능성이 있다면 유망하다

(2) 유망하지 않다(nonpromising)

• 해가 될 가능성이 없다면 유망하지 않다

(3) 가지치기(pruning)

• 유망하지 않는 노드에 가지 않는 것을 가지치기라고 한다.

 

상태 공간 트리를 DFS(깊이 우선 탐색)을 하는 중 해가 될만한지 검사한 후 유망하지 않다고 결정되면 그 노드의 부모로 돌아가(Backtraking) 후 다음 부모 노드의 자식 노드를 탐색합니다.

 

4. N-Queen 문제

Backtraking의 가장 기본적인 문제이다.

문제 : 서양 장기판에 어떤 두 여왕말도 같은 행, 열 대각선에 있지 않도록 n개 여왕말을 놓을 수 있는 방법의 수를 구하는 프로그램을 작성하시오.

 

(1) 퀸이 이동할 수 있는 위치

상하좌우 및 대각선으로 거리 제한 없이 한 방향으로 이동이 가능하다.

 

(2) 유망 조건

(1) 같은 행에 있으면 안 된다

일차원 배열을 이용해서 각 행에 여왕말 1개만 올 수 있도록 한다.

(2) 같은 열에 있으면 안 된다.

promising() method를 이용해서 같은 열에 있는지 검사한다. 

(3) 대각선에 위치하면 안 된다.

promising() method를 이용해서 대각선에 위치하였는지 검사한다.

 

* 대각선 검사

ex) 3,1위치에 여왕말이 있고 6,4위치에 여왕말이 있다고 생각해보자.

|3-6| == |1-4|

두 위치의 행의 차이의 절댓값과 열의 차이의 절댓값이 같다면 두 말은 대각선에 위치해 있다.

 

(3) 소스코드

import java.util.Scanner;

public class BF_9663 {
    static int[] chess;
    static int N;
    static int count;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        chess = new int[N];
        backtracking(0);
        System.out.println(count);
    }
    static void backtracking(int depth) {
        if(depth == N) {
            count++;
            return;
        }
        else {
            for (int i = 0; i <N; i++) {
                chess[depth] = i;
                if(promising(depth)) {
                    backtracking(depth+1);
                }
            }
        }

    }
    static Boolean promising(int col) {
        for (int i = 0; i < col; i++) {
            if(chess[col] == chess[i]) {
                return false;
            }
            else if (Math.abs(col - i) == Math.abs(chess[col] - chess[i])){
                return false;
            }
        }
        return true;
    }
}