C++で2つの文字列を一致させるために必要な最小操作回数を求める方法

問題の概要

2つの文字列 str1 と str2 が与えられます。どちらの文字列も「a」と「b」のみで構成されており、長さは等しく、それぞれに1つの _（空きスペース）が含まれています。目標は、次の操作を最小回数だけ実行して、最初の文字列を2番目の文字列へ変換することです。

• _ が位置 i にあるとき、_ は位置 i+1 または i-1 の文字と入れ替えることができます。
• 位置 i+1 と i+2 の文字が異なる場合、_ は位置 i+1 または i+2 の文字と入れ替えることができます。
• 同様に、位置 i-1 と i-2 の文字が異なる場合、_ は位置 i-1 または i-2 の文字と入れ替えることができます。

たとえば、str1 = "aba_a"、str2 = "_baaa" の場合、str1 を str2 に変換するには2回の操作が必要です。

1. str1 = "ab_aa"（str1[2] と str1[3] を交換）
2. str2 = "_baaa"（str1[0] と str1[2] を交換）

アルゴリズム

この問題は、各文字列の状態を「ノード」、操作を「辺」とみなすことでグラフ探索の問題として捉えられます。幅優先探索（BFS）を使えば、開始状態から近い順に状態を調べていくため、目的の文字列に初めて到達した時点の移動回数が必ず最小となります。

1. 文字列に対して単純な幅優先探索（BFS）を適用します。BFSで使用するキューの要素は (str, pos) のペアで、pos は文字列 str 内における _ の位置を表します。
2. 同時に、vis というマップを管理し、文字列をキー、その文字列に到達するまでの最小移動回数を値として保存します。これにより、同じ状態を二度以上探索する無駄を防ぎます。
3. キューから取り出した各文字列 str について、前述の4つの条件に基づいて新しい文字列 tmp を生成し、vis マップを vis[tmp] = vis[str] + 1 として更新します。
4. キューが空になるか、目的の文字列が得られる（tmp == B）まで、上記の手順を繰り返します。
5. 目的の文字列が得られた時点で vis[str] + 1 を返します。これが A を B に変換するために必要な最小操作回数です。

C++での実装例

#include <iostream>
#include <string>
#include <unordered_map>
#include <queue>
using namespace std;
int transformString(string str, string f){
    unordered_map<string, int> vis;
    int n;
    n = str.length();
    int pos = 0;
    for (int i = 0; i < str.length(); i++) {
       if (str[i] == '_') {
          pos = i;
          break;
       }
    }
    queue<pair<string, int> > q;
    q.push({ str, pos });
    vis[str] = 0;
    while (!q.empty()) {
       string ss = q.front().first;
       int pp = q.front().second;
       int dist = vis[ss];
       q.pop();
       if (pp > 0) {
          swap(ss[pp], ss[pp - 1]);
          if (!vis.count(ss)) {
             if (ss == f) {
                return dist + 1;
                break;
             }
             vis[ss] = dist + 1;
             q.push({ ss, pp - 1 });
          }
          swap(ss[pp], ss[pp - 1]);
       }
       if (pp < n - 1) {
          swap(ss[pp], ss[pp + 1]);
          if (!vis.count(ss)) {
          if (ss == f) {
             return dist + 1;
             break;
          }
          vis[ss] = dist + 1;
          q.push({ ss, pp + 1 });
        }
       swap(ss[pp], ss[pp + 1]);
    }
    if (pp > 1 && ss[pp - 1] != ss[pp - 2]) {
       swap(ss[pp], ss[pp - 2]);
       if (!vis.count(ss)) {
          if (ss == f) {
             return dist + 1;
             break;
          }
          vis[ss] = dist + 1;
          q.push({ ss, pp - 2 });
       }
       swap(ss[pp], ss[pp - 2]);
    }
    if (pp < n - 2 && ss[pp + 1] != ss[pp + 2]) {
       swap(ss[pp], ss[pp + 2]);
       if (!vis.count(ss)) {
          if (ss == f) {
             return dist + 1;
             break;
          }
          vis[ss] = dist + 1;
          q.push({ ss, pp + 2 });
       }
       swap(ss[pp], ss[pp + 2]);
       }
   }
   return 0;
}
int main(){
    string str1 = "aba_a";
    string str2 = "_baaa";
    cout << "Minimum required moves: " << transformString(str1, str2) << endl;
    return 0;
}

出力

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Minimum required moves: 2

まとめ

本記事では、_（空きスペース）を含む2つの文字列を、隣接交換および条件付きの2マス交換という操作で一致させる際の最小操作回数を、C++と幅優先探索（BFS）によって求める方法を解説しました。探索済みの状態をマップで管理することで計算量を抑えつつ、BFSの性質により最短手順を保証できる点がポイントです。