[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라는 이름 때문에 생각의 틀을 깨기가 쉽지 않다.