記事の内容

2024年7月6日に開催されたAtCoderのABC。
そこで出題されたD問題がグラフ理論の練習問題として私にピッタリでした。
復習のために記事にして公開しようと思います。

問題　D - Go Stone Puzzle

問題の詳細をリンク先をご覧ください。

問題の公式解説はこちら。
https://atcoder.jp/contests/abc361/editorial/10354

状態数、次の一手の数がともに十分小さいため、BFS（幅優先探索）が使えそう。

文字列をグラフに見立てます。
すると、重みなしグラフの最短経路問題に翻訳することができます。

まずはPythonコードの全体像です

くどいくらいコメント入れてます。

from collections import deque  

N = int(input())  
S = input().strip()  
T = input().strip()  

start = [None] * (N+2)  # 初期状態を格納するリストを作成（両端にNoneを追加）
goal = [None] * (N+2)   # 目標状態を格納するリストを作成（両端にNoneを追加）

for i in range(N):  
    start[i] = S[i]  # 初期状態の各文字をstartリストに格納
    goal[i] = T[i]   # 目標状態の各文字をgoalリストに格納

def bfs(start, goal):  # 幅優先探索を行う関数を定義
    if sorted(S) != sorted(T):  # SとTの文字構成が異なる場合は変換不可能
        return -1

    queue = deque([(start, 0)])  # 探索キューを初期化（初期状態とステップ数0）
    visited = set()  # 訪れた状態を記録するセット
    visited.add(tuple(start))  # 初期状態を訪問済みとしてマーク

    while queue:  # キューが空になるまで探索を続ける
        current, steps = queue.popleft()  # キューから状態とステップ数を取り出す

        if current == goal:  # 現在の状態が目標状態と一致したら
            return steps  # ステップ数を返して終了

        for i in range(N+1):  # 全ての可能な移動元を試す
            if current[i] is None or current[i+1] is None:  # 移動元が無効な場合はスキップ
                continue
            for j in range(N+1):  # 全ての可能な移動先を試す
                if j == i:  # 移動元と移動先が同じ場合はスキップ
                    continue
                if current[j] is None and current[j+1] is None:  # 移動先が空いている場合
                    new_state = current[:]  # 現在の状態をコピー
                    new_state[j], new_state[j+1] = current[i], current[i+1]  # 文字を移動
                    new_state[i], new_state[i+1] = None, None  # 移動元を空にする
                    new_tuple = tuple(new_state)  # 新しい状態をタプルに変換（ハッシュ可能にするため）
                    if new_tuple not in visited:  # 新しい状態が未訪問の場合
                        visited.add(new_tuple)  # 新しい状態を訪問済みとしてマーク
                        queue.append((new_state, steps + 1))  # 新しい状態をキューに追加

    return -1  # 目標状態に到達できなかった場合

print(bfs(start, goal))  # BFSを実行し、結果を出力

コードのポイント

queueには、文字列のリストとステップ数をタプルにしたものを格納する。
visitedの型はセット。訪問済みの文字列（リスト）をタプルにして格納する。
「２個並んでいる石を、２個並んでいる空きマスに移動させる」をどのようにコードで表現するかに注意する。条件を考慮しつつ、二重ループで表現できる。

簡単な例で実験

N = 3
S = 'BWB'
T = 'BBW'

queueとvisitedの中身の遷移が分かりやすくなるように、簡単な例で実験します。ただし、今回の例では、ゴール状態に変化することはできません。出力結果は−１です。あくまでも、遷移の様子を確かめるための利用にしてください。

実験結果

whileループの中でのqueueとvisitedの遷移をprintで可視化した結果です。queueとvisitedの順に出力しています。

deque([(['B', 'W', 'B', None, None], 0)])
{('B', 'W', 'B', None, None)}
---------------------------
deque([([None, None, 'B', 'B', 'W'], 1), (['B', None, None, 'W', 'B'], 1)])
{('B', None, None, 'W', 'B'), ('B', 'W', 'B', None, None), (None, None, 'B', 'B', 'W')}
---------------------------
deque([(['B', None, None, 'W', 'B'], 1), (['B', 'B', None, None, 'W'], 2)])
{('B', None, None, 'W', 'B'), ('B', 'B', None, None, 'W'), ('B', 'W', 'B', None, None), (None, None, 'B', 'B', 'W')}
---------------------------
deque([(['B', 'B', None, None, 'W'], 2)])
{('B', None, None, 'W', 'B'), ('B', 'B', None, None, 'W'), ('B', 'W', 'B', None, None), (None, None, 'B', 'B', 'W')}
---------------------------

この可視化により、BFSアルゴリズムの様子がわかりやすくなったと思います。

関連記事