841. Keys and Rooms - medium
문제
There are N rooms and you start in room 0. Each room has a distinct number in 0, 1, 2, …, N-1, and each room may have some keys to access the next room.
Formally, each room i has a list of keys rooms[i], and each key rooms[i][j] is an integer in [0, 1, …, N-1] where N = rooms.length. A key rooms[i][j] = v opens the room with number v.
Initially, all the rooms start locked (except for room 0).
You can walk back and forth between rooms freely.
Return true if and only if you can enter every room.
제한사항
- 1 <= rooms.length <= 1000
- 0 <= rooms[i].length <= 1000
- The number of keys in all rooms combined is at most 3000.
입출력 예
1
2
3
4
5
6
7
8
9
Example 1:
Input: [[1],[2],[3],[]]
Output: true
Explanation:
We start in room 0, and pick up key 1.
We then go to room 1, and pick up key 2.
We then go to room 2, and pick up key 3.
We then go to room 3. Since we were able to go to every room, we return true.
1
2
3
4
5
Example 2:
Input: [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can't enter the room with number 2.
풀이
- DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
bool canVisitAllRooms(vector<vector<int>>& rooms) {
// 방을 방문 했다면 false, 방문하지 않았다면 true
vector<bool> visited(rooms.size(), true);
stack<int> s;
// DFS
s.push(0);
while(!s.empty()){
auto index = s.top();
s.pop();
// 현재 index의 방을 방문한 것으로 저장
visited[index] = false;
// 현재 rooms안의 키를 각각 stack에 저장
for(const auto& sub : rooms[index]){
// 방문한적이 없는 키만 stack에 저장
if(visited[sub]){
s.push(sub);
}
}
}
// 방문한적 없는 방이 있다면 false
for(const auto& checker : visited){
if(checker){
return false;
}
}
return true;
}
};