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
'컴퓨터공학 > LeetCode 1000' 카테고리의 다른 글
[LeetCode] 1971. Find if Path Exists in Graph (0) | 2022.12.21 |
---|---|
[LeetCode] 1066. Campus Bikes II (0) | 2022.12.21 |
[LeetCode] 739. Daily Temperatures (0) | 2022.12.20 |
[LeetCode] 2272. Substring With Largest Variance (0) | 2022.12.09 |
[LeetCode] 323. Number of Connected Components in an Undirected Graph (0) | 2022.12.08 |