【LeetCode】841. Keys and Rooms 解答・解説【Python】

はじめに
1. ポイント
詳細
1. 問題
  1. 原文
  2. 内容(和訳)
2. 解答
  1. 解答1：Python, stack
  2. 解答2：Python, stack
終わりに
1. 補足・参考・感想
2. 他の問題もどうぞ

はじめに

LeetCodeの問題を解答します。

なるべく、問題の和訳と詳細なコメントを書いています。

余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。

これまでこのサイトでメモしてきた問題はこのページに全て載せています。

LeetCode 解答・解説記事一覧

二分探索、連結リストなど、テーマを絞って集中的に解きたい方は以下の記事が有用です。

LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。

また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。

はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。

解答前に知っておくと役に立つかもしれない情報

ポイント

- DFS

詳細

問題

原文

There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.

When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.

Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.

Example 1:

Input: rooms = [[1],[2],[3],[]] Output: true Explanation: We visit room 0 and pick up key 1. We then visit room 1 and pick up key 2. We then visit room 2 and pick up key 3. We then visit room 3. Since we were able to visit every room, we return true.

1
2
3
4
5
6
7
8

Input: rooms = [[1],[2],[3],[]]
Output: true
Explanation:
We visit room 0 and pick up key 1.
We then visit room 1 and pick up key 2.
We then visit room 2 and pick up key 3.
We then visit room 3.
Since we were able to visit every room, we return true.

Example 2:

Input: rooms = [[1,3],[3,0,1],[2],[0]] Output: false Explanation: We can not enter room number 2 since the only key that unlocks it is in that room.

1
2
3

Input: rooms = [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can not enter room number 2 since the only key that unlocks it is in that room.

Constraints:

n == rooms.length

2 <= n <= 1000

0 <= rooms[i].length <= 1000

1 <= sum(rooms[i].length) <= 3000

0 <= rooms[i][j] < n

All the values of rooms[i] are unique.

内容(和訳)

n 個の部屋があり、0 から n – 1 まで番号が付けられています。部屋 0 以外はすべて施錠されています。すべての部屋を訪問することを目指しています。ただし、鍵を持っていなければ施錠された部屋に入室できません。

部屋を訪問すると、部屋ごとに異なる鍵のセットを見つける場合があります。各鍵には番号が付けられており、その番号に対応する部屋のロックを解除できます。すべての部屋のロックを解除するために、すべての鍵を持ち出すことができます。

rooms 配列が与えられる場合、rooms[i] は i 番目の部屋を訪問した場合に取得できる鍵のセットです。すべての部屋を訪問できる場合は true、そうでない場合は false を返します。

※Bardによる翻訳

解答

解答1：Python, stack

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        visited = set()
        dict_rooms = {}
        stack = []

        #各部屋内にある鍵をリストとして辞書に記録
        for i in range(len(rooms)):
            dict_rooms[i] = rooms[i]

        #最初の部屋にある鍵をstackに追加
        for i in dict_rooms[0]:
            stack.append(i)

        #visitedに追加することで、最初の部屋を訪問済として記録
        visited.add(0)

        #stackが0よりも大きい限り繰り返す
        while len(stack) > 0:
            #stackから要素を取得
            current = stack.pop()
            #visitedに追加して訪問済みであることを記録
            visited.add(current)
            #dict_rooms[cuurent]には、current番目の部屋内にある鍵がリストとして保持されている
            for i in dict_rooms[current]:
                #visitedに記録されていなければ、stackに追加
                if i not in visited:
                    stack.append(i)
        #部屋の数と訪問済みの部屋の数が一致したらTrueを返す
        return len(dict_rooms) == len(visited)

class Solution:

def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:

visited = set()

dict_rooms = {}

stack = []

#各部屋内にある鍵をリストとして辞書に記録

for i in range(len(rooms)):

dict_rooms[i] = rooms[i]

#最初の部屋にある鍵をstackに追加

for i in dict_rooms[0]:

stack.append(i)

#visitedに追加することで、最初の部屋を訪問済として記録

visited.add(0)

#stackが0よりも大きい限り繰り返す

while len(stack) > 0:

#stackから要素を取得

current = stack.pop()

#visitedに追加して訪問済みであることを記録

visited.add(current)

#dict_rooms[cuurent]には、current番目の部屋内にある鍵がリストとして保持されている

for i in dict_rooms[current]:

#visitedに記録されていなければ、stackに追加

if i not in visited:

stack.append(i)

#部屋の数と訪問済みの部屋の数が一致したらTrueを返す

return len(dict_rooms) == len(visited)

解答2：Python, stack

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        #訪問済みの部屋を記録する変数
        visited_rooms = set()
        #訪問予定の部屋番号を保持する変数
        stack = [0]
        
        #stackに要素がある限り繰り返す
        while stack:
            #変数roomに、今回訪問する部屋を取得
            room = stack.pop()
            #変数visited_roomsに変数roomの値を追加し、訪問済みとして記録
            visited_rooms.add(room)
            #room番目の部屋内にある鍵全てに対して処理
            for key in rooms[room]:
                #未訪問の部屋番号を持つ鍵があれば、stackについか
                if key not in visited_rooms:
                    stack.append(key)
        #部屋数と訪問済みの数が一致したらTrueを返す
        return len(visited_rooms) == len(rooms)

class Solution:

def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:

#訪問済みの部屋を記録する変数

visited_rooms = set()

#訪問予定の部屋番号を保持する変数

stack = [0]

#stackに要素がある限り繰り返す

while stack:

#変数roomに、今回訪問する部屋を取得

room = stack.pop()

#変数visited_roomsに変数roomの値を追加し、訪問済みとして記録

visited_rooms.add(room)

#room番目の部屋内にある鍵全てに対して処理

for key in rooms[room]:

#未訪問の部屋番号を持つ鍵があれば、stackについか

if key not in visited_rooms:

stack.append(key)

#部屋数と訪問済みの数が一致したらTrueを返す

return len(visited_rooms) == len(rooms)

終わりに

補足・参考・感想

問題を分類しました。テーマごとに集中して問題を解くことができます。

LeeetCodeの問題をアルゴリズムとデータ構造による分類

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめました。

解答前に知っておくと役に立つかもしれない情報

他の問題もどうぞ

前：450. Delete Node in a BST

次：216. Combination Sum III

LeetCode 解答・解説記事一覧