【Python】BFSで動物が停止したときの最終的な向きを求めるプログラム

問題の概要

文字列 s は、いくつかの動物の初期状態を表しています。各動物は次の3種類のいずれかの値を取ります。

• L: 動物が左へ移動することを表します

• R: 動物が右へ移動することを表します

• @: 動物がその場に静止していることを表します

ある方向へ移動中の動物は、進行方向にある他の動物を押し流しながら移動していきます。ただし、反対方向から同じタイミングで力を受けると、その場で静止します。すべての動物が停止したときの、それぞれの最終的な向きを求めるのがこの問題の目的です。

たとえば、入力が s = "@@L@R@@@@L" の場合、出力は "LLL@RRRLLL" となります。

解き方のアプローチ(BFS)

この問題は幅優先探索(BFS)を使うと効率的に解けます。力は時間ステップごとに隣接するマスへと伝わっていくため、「同じレベル(同時刻)に反対方向の力が同じマスへ到達した場合、その動物は静止する」という性質を利用できます。

具体的な手順は以下の通りです。

• levels := 文字列 s と同じ長さのリストを作成し、すべて -1 で初期化する

• q := 両端キュー(deque)を用意する

• idx を 0 から s の長さまで順に処理する:

  • s[idx] が "R" または "L" の場合、q の末尾に (idx, 0, s[idx]) を追加する

• l := 文字列 s を文字のリストに変換したもの

• q が空になるまで以下を繰り返す:

  • (idx, new_level, dir) := q の先頭から要素を取り出す

  • levels[idx] が -1 の場合(まだ力が届いていないマス):

    • levels[idx] := new_level とし、l[idx] := dir を設定する

    • dir が "R" かつ idx + 1 が範囲内なら、q に (idx + 1, new_level + 1, dir) を追加する

    • dir が "L" かつ idx - 1 が 0 以上なら、q に (idx - 1, new_level + 1, dir) を追加する

  • levels[idx] が new_level と等しい場合(同時に別方向の力が到達):

    • l[idx] が dir と異なるなら、l[idx] := "@" として静止状態にする

• 最後に、l の要素を連結した文字列を返す

実装例

以下にPythonでの実装例を示します。

from collections import deque
class Solution:
    def solve(self, s):
        levels = [-1 for i in s]
        q = deque()
        for idx in range(len(s)):
            if s[idx] == "R" or s[idx] == "L":
                q.append((idx, 0, s[idx]))
        l = list(s)
        while q:
            idx, new_level, dir = q.popleft()
            if levels[idx] == -1:
                levels[idx] = new_level
                l[idx] = dir
                if dir == "R" and idx + 1 < len(l):
                    q.append((idx + 1, new_level + 1, dir))
                elif dir == "L" and idx - 1 >= 0:
                    q.append((idx - 1, new_level + 1, dir))
            elif levels[idx] == new_level:
                if l[idx] != dir:
                    l[idx] = "@"
        return "".join(l)
ob = Solution()
s = "@@L@R@@@@L"
print(ob.solve(s))

入力

"@@L@R@@@@L"

出力

LLL@RRRLLL

動作の解説

入力 "@@L@R@@@@L" の場合、力は次のように伝わります。

• インデックス2の「L」: 左方向へ伝わり、インデックス0〜2が「L」になる

• インデックス4の「R」: 右方向へ伝わり、インデックス4〜7が「R」になる

• インデックス9の「L」: 左方向へ伝わり、インデックス8〜9が「L」になる

インデックス3には、左の「L」と右の「R」が互いに離れる方向へ移動するため、どちらの力も届きません。そのため「@」のまま静止します。このようにBFSでは、力が届いた順序(レベル)を記録することで、衝突による静止状態を正確に判定できます。