ぷよぷよ、なんて実装の難しいプログラムであろうか。
…多くは対戦AIなどが語られるが、一人用の実装でも難易度は十分に高い。

そこで、本記事では競プロでお馴染みのデータ構造「素集合データ構造(Union Find木)」を利用して、実装をちょっとだけでも楽にできるんだぜ…という話をしてみる。

どこで使う？

同じ色のぷよを繋がりを消去
消去したぷよの数を計算

…こんなものだが
従来使われていた探索アルゴリズムでは、とにかく実装が面倒なのである。 なんとなく想像はつくと思うので詳細は省略するが、個人的にはおそらく探索よりもUnionFind木を利用する方が圧倒的に実装が楽であると思う。
ただ、メモリは探索よりも消費する。…といっても、実用範囲ではせいぜい80個分くらいの配列が付け足されるだけなので、マシンにとっちゃもはや「ない」ようなもんでしょう(初心者観点から)
計算効率もちょっと悪いが、同じく雀の涙程度である。

Union Find木とはなにか

初めて知る人はこちらのページを参考にしてほしい。良い解説である。https://qiita.com/ofutonfuton/items/c17dfd33fc542c222396

動作確認はオンラインジャッジより行うのが良い。以下はAtCoderのもの。https://atc001.contest.atcoder.jp/tasks/unionfind_a

使い方

とりあえず、わかりやすくイメージできるように、次のようなぷよの配列があると仮定して考えてみよう。


\ ⬜️⬜️⬜️⬜️⬜️⬜️　/  0, 1, 2, 3, 4, 5
/ ⬜️⬜️⬜️⬜️⬜️⬜️　\  6, 7, 8, 9,10,11
\ ⬜️⬜️⬜️⬜️⬜️⬜️　/ 12,13,14,15,16,17
/ ⬜️⬜️⬜️⬜️⬜️⬜️　\ 18,19,20,21,22,23
\ ⬜️⬜️⬜️⬜️⬜️⬜️　/ 24,25,26,27,28,29
/ 🟥⬜️⬜️⬜️⬜️⬜️　\ 30,31,32,33,34,35
\ 🟩⬜️⬜️⬜️⬜️⬜️　/ 36,37,38,39,40,41
/ 🟥🟦⬜️⬜️⬜️⬜️　\ 42,43,44,45,46,47
\ 🟦🟦🟦🟩🟩🟩　/ 48,49,50,51,52,53
/ 🟥🟥🟧🟩🟥🟩　\ 54,55,56,57,58,59
\ 🟥🟩🟩🟧🟧🟥　/ 60,61,62,63,64,65
/ 🟩🟧🟧🟥🟥🟩　\ 66,67,68,69,70,71

左は置かれているぷよ、右はそれぞれの配列を識別する番号を表す。
(任意の番号をnとおくと、xy座標型には (n%6,n/6) として変換できる。 )

今に発火せんとしている。

この状態から、まずこれら72個すべての配列の要素において、それらをパラメータとしたUnion Find木を定義する。

そして

横に隣り合っている要素同士(13-15, 63-64など)
縦に隣り合っている要素同士(17-23, 43-49など)

のすべての組み合わせにおいて、「その座標にあるぷよの種類が同じであればuniteする」という作業を行う。
すると、


\ ⬜️⬜️⬜️⬜️⬜️⬜️　/  0, 0, 0, 0, 0, 0
/ ⬜️⬜️⬜️⬜️⬜️⬜️　\  0, 0, 0, 0, 0, 0
\ ⬜️⬜️⬜️⬜️⬜️⬜️　/  0, 0, 0, 0, 0, 0
/ ⬜️⬜️⬜️⬜️⬜️⬜️　\  0, 0, 0, 0, 0, 0
\ ⬜️⬜️⬜️⬜️⬜️⬜️　/  0, 0, 0, 0, 0, 0
/ 🟥⬜️⬜️⬜️⬜️⬜️　\ 30, 0, 0, 0, 0, 0
\ 🟩⬜️⬜️⬜️⬜️⬜️　/ 36, 0, 0, 0, 0, 0
/ 🟥🟦⬜️⬜️⬜️⬜️　\ 42,43, 0, 0, 0, 0
\ 🟦🟦🟦🟩🟩🟩　/ 43,43,43,51,51,51
/ 🟥🟥🟧🟩🟥🟩　\ 54,54,56,51,58,51
\ 🟥🟩🟩🟧🟧🟥　/ 54,61,61,63,63,65
/ 🟩🟧🟧🟥🟥🟩　\ 66,67,67,69,69,71

となる。

こうなればあとは簡単である。

存在するrootごとにその要素の数を数え(30なら1個、36なら1個………43なら4個、51なら5個……71なら1個　といった具合。0はたくさんあるが、ぷよの置かれていない集合なので無視する)、4つ以上なら消す対象の木としてrootの数値を保持しておく。
そしてもう一度ループしてその木の要素のぷよを消し、その数に応じてスコアを加算。

ぷよが消せたら、空中に浮いているぷよを落としてもう一度この作業を行う。そして、消せるぷよがなくなるまで繰り返したら次のループへ。

という感じ。おしまい。

備考

僕が実際に実装した例。なお、上記のアルゴリズムとは若干異なる部分もいくつかあるが、仕組みは同じである。
https://github.com/Perukii/PeruPuyo