[LeetCode] 841. Keys and Rooms

841. Keys and Rooms

Medium

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.

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.

 

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.

---

문제 풀이

• 방의 열쇠가 들어가있는 방의 배열이 주어진다. 
• 2차원 배열이며 각각의 배열에는 번호들이 들어있는데, 이 번호는 그 번호의 방으로 들어갈 수 있는 키이다.
• 0번인 첫번째 방은 열쇠없이도 들어갈 수 있지만 다른방은 열쇠가 있어야한다.
• 첫번째 방으로 들어가서 열쇠를 얻고 들어갈 수 있는 모든 방을 탐색하여 주어진 rooms에 들어갈 수 있는지를 구해야한다.
• 제한 조건을 보면 방의 개수가 최대 1000 이기 때문에 완전탐색 접근을 시도해도 된다. 
• DFS, BFS를 사용할 수 있으며, 모든 방의 열쇠를 모든 방이 가지고 있을 때도 있기 때문에 BFS가 성능면에서는 조금 빠를것이라고 예상된다. 
• 방의 개수를 구하고 BFS를 구축한다.
• 큐에 현재 방번호와 그 방에 들어있는 열쇠들의 배열을 넣는다. 
• 한번 들어갔던 방은 피하기위해 visited 배열을 사용하여 막는다. 
• 방의 개수에서 0번 방의 개수를 뺀 n을 사용하여, 새로운 방문을 열었을때마다 개수를 제거한다.
• 결과적으로 n값이 0이되면 모든 방을 들어갔다 온것이다. 
• 큐가 바닥 날때까지 n의 개수가 0이되지 않으면 들어가지 못한 방이 존재하는 것이다. 

소스 코드

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        n = len(rooms) - 1
        visited = [0] * (n + 1)
        visited[0] = 1
        que = []
        que.append((0, rooms[0]))
        while que:
            curr_n, rs = que.pop(0)
            for i in range(len(rs)):
                if visited[rs[i]] == 1: 
                    continue
                visited[rs[i]] = 1
                n -= 1
                if n == 0:
                    return True
                que.append((rs[i], rooms[rs[i]]))
        return False