バックグラウンドでnodeJS(#05):遡及-DFS#15652号#9663号

1.緒論

アルゴリズムを解く問題は通常2つのクラスに分けられ,1つは総数を決定する必要がある問題であり,もう1つは特定の値を探す問題である.

ナビゲーションと検索

前者をナビゲーションと呼び,後者を検索と呼ぶ.
つまり、ナビゲーションは、自分が検索するコンテンツ(たとえば、最適な条件や特定の条件を満たす数)が分からない場合に使用します.検索は、検索するコンテンツと、検索するコンテンツを知っている場合に使用します.

さかのぼる

遡及は、すべての場合の合計数を決定するツリーベースのナビゲーションアルゴリズムです.
遡及は深さ優先ナビゲーション(DFS)と幅優先ナビゲーション(BFS)、DFSはスタック(LIFO)、BFSはキュー(FIFO)を使用する.したがって、すべての場合の数を調べる必要がある場合はDFSを使用することが好ましく、最短距離または最短距離で答えが見つかった場合はBFSを使用することが一般的である.

2. DFS

DFSは、状態空間(すべての場合の数)を表すツリーにおいて次の方向のみを表す方式である.次の分岐点から別の方向に行く方法で、底に着くまで、再び木に登ります.ターゲット値が表示されるまで、この操作を繰り返します.
スタック式であるが、通常は再帰関数として実装される.

// Pseudo code example
// N은 스택의 깊이
function dfs(idx){
  // terminal condition
  if(idx === N){
    ```
      탐색 종료 코드
    ```
    return;
  } else {
    for(let i = 0; i < Stack.length; i++){
      // stack in
      ```
        스택 처리 코드
      ```
      // 재귀함수
      dfs(idx + 1);
      // stack out
      ```
        스택 처리 코드
      ```
    }
  }
}

3.問題15652：NとM（4）

関連する問題はPermutationを出力するが、同じ数の繰り返しが許容されるため、実際には出力の組み合わせの問題である.nCm出力の場合は、上記のDFS例のフォーマットのコードを用いて、このフォーマットのコードを生成することができる.

let [N, M] = require("fs").readFileSync("/dev/stdin").toString().trim().split(" ").map((a) => +a);

let ANSWER = "";
let prefix = [];
function combination(n, count) {
  if (prefix.length == M) {
    ANSWER += prefix.join(" ") + "\n";
    return;
  }
  // 1 ~ N 까지의 자연수를 출력하기 위해 1부터 시작
  for (let i = count; i < n + 1; i++) {
    // prefix stack in till it reaches terminal node
    prefix.push(i);
    // 재귀함수
    combination(n, i);
    // when it reached terminal node, then prefix stack out
    prefix.pop();
  }
}

combination(N, 1);
console.log(ANSWER);

例を使用すると、内部構造の理解が容易になります.let [N, M] = [4, 2]の運転結果は以下の通りです.

4.問題9663：N-Queens

関連する問題は典型的な遡及問題であり、N個のクイーンのN*Nサイズの碁盤上の数を決定する問題である.
通常、碁盤などの例では、問題を解くために2次元配列が作成されますが、この問題では、クイーンの特性上、横線と縦線が同じクイーンを同時に存在させることができないため、碁盤を波円アレイに圧縮することができます.
配列のインデックスをcolumnに設定し、配列の値をrowに設定すると、皇后の配置を表すには1次元配列しか使用できません.
この問題の鍵は、対角線上のクイーンを削除する方法であり、既存の配列のクイーン位置と各配列のインデックスと値の絶対値を配置することで対角線を配置できます.

サンプルコード:Math.abs(array[x] - array[i]) == x - i

最初の方法は、次の展開でこの要件を満たす場合に数を決定する方法でアクセスすることは非常に困難であり、逆に、既存のアレイから可能な展開を決定することは問題解決の鍵となる.

let N = Number(require("fs").readFileSync("test.txt").toString().trim());

let array = new Array(N + 1).fill(0);
let answer = "";
let count = 0;

function dfs(x) {
  // 이번 문제의 stack out은 checker를 통해 구현되었다. 
  // 만약 checker를 통과하지 못한다면 자연스럽게 다음 노드로 넘어가지 못하고 패스된다.
  if (checker(x)) {
    if (x == N) {
      count++;
      // 문제 자체는 개수만 요구하기 때문에 하단의 join 구문은 필요가 없다.
      let coiped = [...array];
      answer += coiped.join(" ") + "\n";
      return;
    }
    // 1~N까지의 체스판을 보여주기 위해 1부터 시작
    // 또한 첫번째 노드가 checker를 통과하기 위해서는 배열의 첫번째 값을 의도적으로 배제해야한다.
    for (let i = 1; i < N + 1; i++) {
      array[x + 1] = i;
      dfs(x + 1);
    }
  }
}

function checker(x) {
  for (let i = 1; i < x; i++) {
    if (array[x] == array[i] || Math.abs(array[x] - array[i]) == x - i) {
    return false;
    }
  }
  return true;
}

dfs(0);
console.log(answer);

参考文献

https://namu.wiki/w/%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9
https://kscodebase.tistory.com/518