C++で解く最小遺伝子変異問題：BFSによる最短変異回数の求め方

長さ8の遺伝子文字列を考えます。この文字列は「A」「C」「G」「T」の4種類の文字のみで構成されています。ここでいう1回の突然変異とは、遺伝子文字列内のたった1文字を別の文字へ変更することを指します。たとえば、「AACCGGTT」を「AACCGGTA」へ変更するのは1回の変異に相当します。

さらに、有効な遺伝子変異をすべて格納した「遺伝子バンク」が与えられます。ある遺伝子が有効な文字列として認められるためには、必ずこのバンクに含まれていなければなりません。

課題は、「start（開始遺伝子）」「end（目標遺伝子）」「bank（遺伝子バンク）」の3つが与えられたとき、startからendへ到達するために必要な最小の変異回数を求めることです。もし変換が不可能な場合は -1 を返します。

たとえば、入力が start = "AACCGGTT"、end = "AAACGGTA"、bank = ["AACCGGTA", "AACCGCTA", "AAACGGTA"] の場合、出力は 2 となります。

解法のアプローチ

この問題は幅優先探索（BFS）を用いて効率的に解けます。各遺伝子をグラフのノードとみなし、「1文字だけ異なる」遺伝子同士を隣接関係として扱うことで、startからendまでの最短経路（＝最小変異回数）を求めることができます。

ポイントとなるのは putStar() 関数です。文字列の各位置を1つずつ「*」に置き換えたパターンを生成することで、「1文字違い」という関係をパターンの一致として表現できます。2つの遺伝子がちょうど1文字だけ異なる場合、それらは必ず同一のパターンを共有します。

アルゴリズムの手順

• putStar(s) 関数を定義します。文字列 s の各位置を「*」に置き換えたパターンを配列 ret に格納して返します。
• メイン処理では、まずグラフ用のマップ graph を定義します。
• バンク内の各遺伝子 s について、putStar(bank[i]) で生成した全パターンに対して、元の遺伝子 s を graph[パターン] に登録します。これにより「同じパターンを持つ遺伝子群」が構築されます。
• キュー q を定義し、start を挿入します。
• 訪問済み集合 visited を定義し、start を挿入します。
• レベル lvl を1から始め、キューが空になるまで以下を繰り返します。
  • 現在のキューのサイズ sz を取得します（レベルごとの一括処理のため）。
  • sz 回だけ次の処理を繰り返します。
    • キューの先頭ノードを取り出します。
    • putStar(node) でパターンを生成します。
    • 各パターン u について、graph[u] に登録された隣接ノード v を順に調べます。
    • v が訪問済みならスキップします。
    • v が end と一致していれば、その時点の lvl を返します。
    • そうでなければ v を visited と q に追加します。
• キューが空になっても end に到達できなければ、-1 を返します。

BFSはレベル（変異回数）ごとに探索を進めるため、end が最初に見つかった時点のレベルがそのまま最小変異回数になります。

実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    vector <string> putStar(string s){
        vector <string> ret;
        for(int i = 0; i < s.size(); i++){
            string temp = s.substr(0, i) + "*" + s.substr(i + 1);
            ret.push_back(temp);
        }
        return ret;
    }
    int minMutation(string start, string end, vector<string>& bank) {
        unordered_map < string, vector <string> > graph;
        for(int i = 0; i < bank.size(); i++){
            string s = bank[i];
            vector <string> out = putStar(bank[i]);
            for(int j = 0; j < out.size(); j++){
                graph[out[j]].push_back(s);
            }
        }
        queue <string> q;
        q.push(start);
        set <string> visited;
        visited.insert(start);
        for(int lvl = 1; !q.empty(); lvl++){
            int sz = q.size();
            while(sz--){
                string node = q.front();
                q.pop();
                vector <string> out = putStar(node);
                for(int i = 0; i < out.size(); i++){
                    string u = out[i];
                    for(int j = 0; j < graph[u].size(); j++){
                        string v = graph[u][j];
                        if(visited.count(v)) continue;
                        if(v == end) return lvl;
                        visited.insert(v);
                        q.push(v);
                    }
                }
            }
        }
        return -1;
    }
};
main(){
    Solution ob;
    vector<string> v = {"AACCGGTA", "AACCGCTA", "AAACGGTA"};
    cout << (ob.minMutation("AACCGGTT", "AAACGGTA", v));
}

入力

"AACCGGTT", "AAACGGTA", {"AACCGGTA", "AACCGCTA", "AAACGGTA"}

出力

2

計算量の目安

N をバンク内の遺伝子の個数、L を遺伝子の長さ（本問では8）とすると、グラフ構築とBFSの探索はそれぞれ各遺伝子につき L 個のパターンを扱うため、時間計算量・空間計算量はともに O(N × L) 程度で抑えられます。遺伝子の長さが固定長であるため、非常に効率的な解法といえます。