백 트래킹 (BackTracking)

백 트래킹은 한 마디로 말하면 되추적이라는 뜻이다.

알고리즘 적으로 말하자면, '유망성'을 판단하여 가능성이 있는 경우의 수만 찾아보는 알고리즘이다.

이전에 배운 BruteForce 알고리즘을 생각해보자.
BruteForce Algorithm 에서는 모든 경우의 수를 찾아 보았기 때문에,
만족하는 값을 100% 찾을 수 있었지만, 자원을 엄청나게 많이 쓴다는 단점을 가지고 있었다.

하지만 BackTracking 알고리즘에서는 가능성이 없는 경우의 수는 찾아보지 않기때문에 자원을 아낄 수 있다는 장점을 가지고 있다.

이것을 가지치기(Pruning)을 통해 효율을 극대화한다고 한다.

BackTracking은 "가능한 모든 방법을 찾아본다" 라는 아이디어를 가진다.
대표적인 방법으로는 DFS(Depth First Search,깊이 우선 탐색)이 있다.

알고리즘 문제

• 백준 15649번 문제
• 중복이 없는 순열을 구하는 문제
• DFS를 통하여 풀이

package back_joon.Data_Structures;
import java.util.*;


// BackTracking
public class b15649 {
    static int[] arr;
    static boolean[] visit;
    public static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();

        arr = new int[M];
        visit = new boolean[N];
        dfs(N,M,0);

        System.out.println(sb);
    }

    public static void dfs(int N,int M,int depth){
        if(depth == M){
            for(int val : arr){
                sb.append(val).append(' ');
            }
            sb.append('\n');
            return;
        }

        for(int i=0;i<N;i++){
            if(!visit[i]){
                visit[i] = true;
                arr[depth] = i+1;
                dfs(N,M,depth + 1);
                visit[i] = false;
            }
        }
    }
}

알고리즘 문제 - 2

• 백준 9663번 문제
• N x N 개의 체스판에서 Queen을 둘 수 있는 방법의 수 구하기
• count 변수를 통한 개수 출력
• 퀸의 공격방식인 가로,세로,대각선 위치 파악 후 가능한 위치에 존재하도록 하는 함수 possible 구현

package back_joon.Data_Structures;
import java.util.Scanner;

// N-Queen 문제
public class b9663 {
    static int N;
    static int count = 0;
    static int[] arr;
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        arr = new int[N];

        backTracking(0);
        System.out.println(count);
    }

    public static void backTracking(int depth){
        if(depth == N){
            count++;
            return;
        }

        for(int i=0;i<N;i++){
            arr[depth] = i;
            if(possible(depth)){
                backTracking(depth+1);
            }
        }
    }

    public static boolean possible(int num){
        for(int i=0;i<num;i++){
            // 같은 행에 존재하는 경우
            if(arr[num] == arr[i]){
                return false;
            }

            // 대각선에 존재하는경우
            else if(Math.abs(num-i) == Math.abs(arr[num] - arr[i])){
                return false;
            }
        }

        return true;
    }
}