Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- LeetCode
- 눈알빠지겠네
- 맛집
- 알고리즘테스트
- 밥먹고
- 발더스모드
- 미앤아이
- 송리단
- 코테
- 발더스3
- 누룽지소금빵
- 코딩테스트
- 나쫌
- 게임
- 버즈2프로
- 취미
- 바질토마토뭐시기
- 3d퍼즐
- 노노그램
- DIY
- 하스스톤
- 토이프로젝트
- javascript
- 서울제빵소
- 메일우유
- 메탈퍼즐
- 천등
- 잠실새내
- 뜨아거
- 발더스게이트
Archives
- Today
- Total
.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] 880. Decoded String at Index (0) | 2023.09.28 |
---|---|
[leetCode/JS] 905. Sort Array By Parity (0) | 2023.09.28 |
[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 |
Comments