さかのぼる

後追いは一言で言えば遡るという意味です.
アルゴリズム的には「有望性がある」と判断し,可能な数だけを探すアルゴリズムである.
以前学んだBreutForceアルゴリズムを考えてみましょう.
BreuteForce Algorithmはすべての場合の数字を検索しました.
100%満足のいく価格を見つけることができますが、欠点は資源消費が大きいことです.
しかし,BackTrackingアルゴリズムでは,不可能な数を見つけることができないため,リソースを節約できるという利点がある.
これは枝を直すことで効率を最大化しているそうです.
BackTrackingのアイデアは「可能な限りの方法を探す」ことです.
代表的な方法として深さ優先探索(DFS)がある.

アルゴリズム問題

白駿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題

Nx N個チェス盤にQueenを置く方法個数を求める

count変数のカウント出力

皇后の攻撃方式:横、縦、対角線の位置を決めて可能な限り位置に存在する関数が可能

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;
    }
}