C++でモバイルキーパッドから生成できるすべてのn桁パターンを出力する方法

問題の概要

この問題では、整数 n が与えられ、モバイルキーパッドのボタンを押すことで形成できるすべてのn桁のパターンを出力することが求められます。ただし、ボタンを押す際には、現在押しているボタンの隣接するボタン(左・右・上・下)しか押せないという制約があります。

従来のモバイルキーパッドの配置

入力例と出力例

具体的な例を見て、問題を理解しましょう。

入力: n = 2
出力: 12 14 21 23 25 32 36 41 45 47 52 54 56 58 63 65 69 74 78 85 87 89 80 96 98

n = 2 の場合、「1」から始まるパターンなら右隣の「2」または下の「4」に移動できるため「12」「14」が生成されます。このように、各開始キーから隣接キーへ順に移動しながら、指定した桁数に達するまで全経路を列挙します。

解決アプローチ:深さ優先探索(DFS)

この問題は深さ優先探索(DFS)を使うことで効率的に解けます。アルゴリズムの流れは以下の通りです。

1. キーパッド上のすべてのキーを順番に選び、それぞれを数値の最初の桁として設定します。
2. 現在の位置から上下左右の隣接キーへ再帰的に移動し、残りの桁を生成します。
3. パターンの長さが n 桁に達したら、そのパターンを出力します。
4. 有効な数字キーのみを対象とし、* や # の位置(-1 で表現)はスキップします。

C++による実装例

上記のアルゴリズムを実装したプログラムは以下の通りです。

#include <bits/stdc++.h>
using namespace std;

// 移動先がグリッド内かつ未訪問かどうかを判定する関数
bool isSafe(int x, int y, bool Visited[][3]) {
    return (x >= 0 && x < 4 && y >= 0 && y < 3 && !Visited[x][y]);
}

// DFSでパターンを生成する関数
void searchNumber(bool visited[][3], int Keypad[][3], int n, string pattern, int x, int y) {
    pattern.push_back((Keypad[x][y] + '0'));
    if (pattern.size() == n) {
        cout<<pattern<<"\t";
        return;
    }
    static int row[] = { 0, 1, 0, -1 };
    static int col[] = { 1, 0, -1, 0 };
    visited[x][y] = true;
    for (int k = 0; k < 4; k++)
        if (isSafe(x + row[k], y + col[k], visited) && Keypad[x + row[k]][y + col[k]] != -1)
    searchNumber(visited, Keypad, n, pattern, x + row[k], y + col[k]);
    visited[x][y] = false;
    pattern.pop_back();
}

// n桁の数値を生成するメイン処理
void GenerateNDigitNumber(int Keypad[][3], int n) {
    bool visited[4][3];
    memset(visited, false, sizeof(visited));
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 3; j++)
            if (Keypad[i][j] != -1)
                searchNumber(visited, Keypad, n, "", i, j);
}

int main() {
    int Keypad[4][3] ={
        { 1, 2, 3 },
        { 4, 5, 6 },
        { 7, 8, 9 },
        { -1, 0, -1 }
    };
    int n = 2;
    cout<<"All "<<n<<" digit number generated from keypad are :\n";
    GenerateNDigitNumber(Keypad, n);
    return 0;
}

コードのポイント解説

• isSafe関数: 移動先の座標(x, y)がキーパッドの4×3グリッド内に収まっているか、また既に訪問済みでないかをチェックします。
• searchNumber関数: 現在のキーをパターンに追加し、n桁に達していれば出力します。未達の場合は上下左右の4方向へ再帰的に探索を行い、戻る際には訪問フラグとパターンを元に戻す(バックトラック)ことで、別の経路を正しく探索できるようにしています。
• GenerateNDigitNumber関数: 訪問管理用の配列を初期化し、無効なキー(* と # は -1 として表現)を除外したうえで、すべてのキーを起点としてDFSを開始します。

実行結果

All 2 digit number generated from keypad are −
12 14 23 25 21 36 32 45 47 41 56 58 54 52 69 65 63 78 74 89 80 87 85 98 96 08

このように、n = 2 の場合にキーパッドの隣接移動で作成可能なすべての2桁パターンが出力されます。「08」のように「0」を含むパターンも、隣接関係(8の下に0がある)を満たしているため有効です。

計算量について

各キーから最大4方向に分岐するため、時間計算量は概ね O(4ⁿ × n) となります。n が大きくなると組み合わせが爆発的に増えるため、実用的には小さい n(2〜4程度)に対して適用するのが現実的です。