Notice
Recent Posts
Recent Comments
Link
.Zzumbong
[leetCode/JS] 841. Keys and Rooms ๋ณธ๋ฌธ
๋์ด๋ [ ๐ฟ ๐ ๐ค ] Hard Medium Easy
๋ฌธ์ ์ค๋ช
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.
n๊ฐ์ ๋ฐฉ์ด ์ฃผ์ด์ง๋ค.
๋ฐฉ์๋ key๊ฐ ๋ค์ด์๋๋ฐ, ์ด key๋ก๋ง ๋ฐฉ์ ์ด ์ ์๋ค. 0๋ฒ ๋ฐฉ์ ์ด๋ ค์๋ค.
๋ชจ๋ ๋ฐฉ์ ๋ฐฉ๋ฌธํ ์ ์๋ค๋ฉด true, ์๋๋ฉด false์ด๋ค.
์ ์ถ๋ ฅ ์
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.
๋ด ์๋ฃจ์
- rooms array์ key๊ฐ ๋ค์ด ์๋ค๊ณ ์๊ฐํ๋ฉด ๋ก์ง์ด ๋ณต์กํด์ง๋ค.
- rooms๋ฅผ tree๋ก ๋ณด๊ณ element๋ ๋ฐฉ๋ฌธํ ์ ์๋ node๋ก ๋ณด๋ฉด ์ฝ๋ค.
- DFS๋ก ๊ฐ ์ ์๋ ๋ชจ๋ ๋ ธ๋๋ฅผ ๋ฐฉ๋ฌธํ๊ณ visited์ index๋ฅผ ๋ด๋๋ค.
- visited์ length, size๋ฅผ ๋น๊ตํ์ฌ ๊ฐ์ผ๋ฉด ๋ชจ๋ ๋ฐฉ๋ฌธํ๊ธฐ ๋๋ฌธ์ true์ด๋ค.
/**
* @param {number[][]} rooms
* @return {boolean}
*/
var canVisitAllRooms = function(rooms) {
const visited = new Set();
const dfs = (roomIndex) => {
if(visited.has(roomIndex)) return;
visited.add(roomIndex);
for(let i = 0; i < rooms[roomIndex].length; i++) {
dfs(rooms[roomIndex][i]);
}
}
dfs(0);
return visited.size === rooms.length;
};
๊ฐ์ํ
- ์๊ฐ๋ณด๋ค key๋ผ๋ ์ด๋ฆ ๋๋ฌธ์ ์๊ฐ์ ํ์ ๊นจ๊ธฐ๊ฐ ์ฝ์ง ์๋ค.
'coding test > leetCode' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[leetCode/JS] 739. Daily Temperatures (0) | 2022.12.18 |
---|---|
[leetCode/JS] 150. Evaluate Reverse Polish Notation (0) | 2022.12.17 |
[leetCode/JS] 232. Implement Queue using Stacks (0) | 2022.12.16 |
[leetCode/JS] 1143. Longest Common Subsequence (0) | 2022.12.15 |
[leetCode/JS] 152. Maximum Product Subarray (0) | 2022.12.14 |
0 Comments