記事の内容
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アルゴリズムの様子がわかりやすくなったと思います。