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

部屋と呼ばれるリストのリストがあるとします。部屋の各インデックスiは部屋を表し、rooms[i]は他の部屋を開くためのさまざまなキーを表します。部屋0は開いていて、私たちはその部屋にいて、他のすべての部屋は施錠されています。開いた部屋の間を自由に移動できます。すべての部屋を開けられるかどうかを確認する必要があります。

したがって、入力がrooms =[[2、0]、[3]、[1]、[]]のようである場合、部屋0から開始し、そのキーを使用して部屋2に進むことができるため、出力はTrueになります。 2. 2号室から1号室に行くことができます。次に、3号室の鍵を持って開きます。つまり、すべてが開かれます。

これを解決するには、次の手順に従います。

• n：=部屋のサイズ
• ready：=単一要素0のリスト
• 見た：=新しいセット
• 準備完了が空でない場合は、
  • u：=準備完了の最後の要素であり、準備完了から削除します
  • 見たとおりにuをマーク
  • 部屋のvごとに[u]、実行します
    • vが表示されない場合は、
      • 準備完了の最後にvを挿入
• seeのサイズが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