C++で金庫のパスワードをクラックするアルゴリズムと実装例

パスワードで保護された金庫を想像してみてください。パスワードは n 桁の数字列で、各桁には 0 ～ k−1 までの先頭 k 個の数字（0, 1, …, k−1）のいずれかが使用されます。この金庫には特別な仕組みがあり、パスワードを入力すると、最後に入力された n 桁が自動的に正規のパスワードと照合されます。

たとえば、正しいパスワードが「563」である場合、「285639」と入力すると、末尾の 3 桁「563」が正しいパスワードと一致するため、金庫は開きます。今回の目的は、入力中のいずれかの時点で確実に金庫が開く、最小長の数字列を 1 つ見つけることです。

たとえば n = 2、k = 2 が与えられた場合、答えは「01100」「00110」「10011」「11001」のいずれかとなります。

デ・ブランジュ列との関係

この問題は、グラフ理論で知られるデ・ブランジュ列（de Bruijn sequence）と深く関連しています。デ・ブランジュ列とは、k 種類の記号からなるすべての長さ n の並びを、それぞれ 1 回以上部分文字列として含む最短の列のことです。深さ優先探索（DFS）を利用することで、そのような列を効率的に構築できます。

解法のステップ

以下の手順に従って問題を解いていきます。

• 訪問済みの文字列を記録するセット visited を定義します。
• s と k を引数に取る関数 dfs() を定義します。
• i を 0 から始めて k 未満の間、1 ずつ増やしながら次の処理を繰り返します。
  • temp := s に数字 i を文字列として連結します。
  • temp が visited に存在しない場合は、次の処理を行います。
    • temp を visited に追加します。
    • temp := temp の 1 文字目を除いた部分文字列に更新します。
    • dfs(temp, k) を再帰的に呼び出します。
    • ret := ret に数字 i を文字列として連結します。
• メインメソッドでは、次のように処理を進めます。
• n == 1 かつ k == 1 の場合は「0」を返します。
• ret と s を空文字列で初期化します。
• i を 0 から n − 1 未満まで 1 ずつ増やしながら、s に「0」を連結します。
• dfs(s, k) を呼び出します。
• i を 0 から n − 1 未満まで 1 ずつ増やしながら、ret に「0」を連結します。
• ret を返します。

それでは、理解を深めるために実際の実装を見てみましょう。

コード例

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   set <string> visited;
   string ret;
   string crackSafe(int n, int k) {
      if(n == 1 && k == 1) return "0";
      ret = "";
      string s = "";
      for(int i = 0; i < n - 1; i++){
         s += "0";
      }
      dfs(s, k);
      for(int i = 0; i < n - 1; i++) ret += "0";
      return ret;
   }
   void dfs(string s, int k) {
      string temp;
      for(int i = 0; i < k; i++){
         temp = s + to_string(i);
         if(!visited.count(temp)){
            visited.insert(temp);
            temp = temp.substr(1);
            dfs(temp, k);
            ret += to_string(i);
         }
      }
   }
};
main(){
   Solution ob;
   cout << (ob.crackSafe(2,2));
}

入力

2
2

出力

01100

まとめ

このアルゴリズムでは、DFS によるバックトラックを活用し、考えられるすべてのパスワード候補を一度だけ通るような最短の数字列を構築しています。処理量は生成される列の長さにほぼ比例し、O(kⁿ × n) 程度に抑えられるため非常に効率的です。デ・ブランジュ列の性質を応用した、大変美しい解法と言えるでしょう。