.Zzumbong

[leetCode/JS] 841. Keys and Rooms ๋ณธ๋ฌธ

coding test/leetCode

[leetCode/JS] 841. Keys and Rooms

์ญ˜๋ด‰ 2022. 12. 20. 09:53

๋‚œ์ด๋„ [ ๐Ÿ‘ฟ ๐Ÿ˜Š ๐Ÿค” ] 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