Pythonですべての部屋のロックを解除できるかどうかを確認するプログラム

リストの中にリストが格納された rooms というデータがあるとします。各インデックス i は部屋番号を表し、rooms[i] にはその部屋から他の部屋を開けるための鍵のリストが入っています。部屋0は最初から開いており、自分はそこにいる状態です。それ以外の部屋はすべて施錠されています。開いた部屋の間は自由に移動できるものとして、すべての部屋を開けられるかどうかを判定する必要があります。

例えば、入力が rooms = [[2, 0], [3], [1], []] の場合、出力は True になります。部屋0からスタートし、持っている鍵2を使って部屋2へ移動できます。部屋2には鍵1があるので部屋1を開け、さらに部屋1にある鍵3で部屋3も開けられます。このようにしてすべての部屋が開くため、結果は True となります。

解決のためのアルゴリズム

この問題は、グラフの探索（DFS/BFS）の考え方を使うことで効率的に解けます。手順は以下の通りです。

• n := rooms のサイズ（部屋の総数）
• ready := 要素0のみを含むリスト（探索待ちの部屋）
• seen := 新しいセット（訪問済みの部屋を記録）
• ready が空になるまで以下を繰り返す
  • u := ready の最後の要素を取り出して削除
  • u を seen に追加（訪問済みとしてマーク）
  • rooms[u] 内の各 v について、v が未訪問なら ready の末尾に追加
• seen のサイズが n と一致すれば true、そうでなければ false を返す

それでは、実際の実装を見て理解を深めましょう。

サンプルコード

class Solution:
    def solve(self, rooms):
        n = len(rooms)

        ready = [0]
        seen = set()

        while ready:
            u = ready.pop()
            seen.add(u)

            for v in rooms[u]:
                if v not in seen:
                    ready.append(v)

        return len(seen) == n

ob = Solution()
rooms = [
    [2, 0],
    [3],
    [1],
    []
]
print(ob.solve(rooms))

入力

rooms = [[2, 0],[3],[1],[]]

出力

True

コードのポイント

この実装では、スタック（LIFO）を使った深さ優先探索（DFS）と同じ構造になっています。ready.pop() で末尾から要素を取り出し、訪問済みセット seen で重複探索を防いでいます。計算量は部屋数を n、鍵の総数を k とすると O(n + k) となり、非常に効率的です。また、ループが閉じている場合（同じ部屋の鍵が何度も出現する場合）でも、seen によるチェックのおかげで無限ループに陥ることはありません。