AtCoder ABC【D-Go Stone Puzzle】をPythonで解いてみた「グラフ理論」のいい練習

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



## 問題　D - Go Stone Puzzle
https://atcoder.jp/contests/abc361/tasks/abc361_d

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

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

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

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


## まずはPythonコードの全体像です
くどいくらいコメント入れてます。
```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`の型はセット。訪問済みの文字列（リスト）をタプルにして格納する。
* 「２個並んでいる石を、２個並んでいる空きマスに移動させる」をどのようにコードで表現するかに注意する。条件を考慮しつつ、二重ループで表現できる。


## 簡単な例で実験

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


## 関連記事
* [論理学って何を扱うの？論理学入門](https://qiita.com/kyogoku_meta/items/7dc1c17f78bc36d11346)
* [線形代数の「背景と概念」をもっとよく分かりたい【数学弱者・凡人のための線形代数入門】](https://qiita.com/kyogoku_meta/items/077e9972dcd7b08d6473)
* [弱者・凡人のための競技プログラミング入門『競技プログラミングの鉄則』本を使いこなしたい ①二分探索](https://qiita.com/kyogoku_meta/items/91b32773f045d0ef560b)
* [弱者・凡人のための競プロ入門『競技プログラミングの鉄則』を使いこなしたい！『グラフ』編](https://qiita.com/kyogoku_meta/items/1c735119b0b93cb24d0e)