Leetcode 841. Keys and Rooms

첫 번째 코드(DFS):

/**
 * @param {number[][]} rooms
 * @return {boolean}
 */
var canVisitAllRooms = function(rooms) {
    const visited = [];

    const dfs = (curRoom) => {
      visited.push(curRoom);

      for (const key of rooms[curRoom]) {
        if (!visited.includes(key)) {
          dfs(key);
        }
      }
    };

    dfs(0);

    return visited.length === rooms.length;
};

• DFS 함수 (dfs):
  • 현재 방을 방문한 것으로 표시하고 visited 배열에 추가
  • 현재 방에서 얻은 모든 키에 대해, 이미 방문한 방이 아니라면 재귀적으로 dfs 함수를 호출
• 전체 로직:
  • 0번 방부터 시작하여 DFS를 통해 방문 가능한 모든 방을 체크
  • 최종적으로 visited.length와 rooms.length를 비교하여 모든 방을 방문했는지 여부를 반환

두 번째 코드(DFS 개선):

/**
 * @param {number[][]} rooms
 * @return {boolean}
 */
var canVisitAllRooms = function(rooms) {
    const visited = new Set();
    
    const dfs = (room) => {
        if (visited.has(room)) return;
        
        visited.add(room);
        
        for (const key of rooms[room]) {
            dfs(key);
        }
    };
    
    dfs(0);
    
    return visited.size === rooms.length;
};

• DFS 함수 (dfs):
  • 현재 방을 방문한 것으로 표시하고 visited Set에 추가
• 나머지는 동일.

세 번째 코드(BFS):

/**
 * @param {number[][]} rooms
 * @return {boolean}
 */
var canVisitAllRooms = function(rooms) {
    const visited = new Set();
    const queue = [0];

    while (queue.length > 0) {
        const curRoom = queue.shift();
        visited.add(curRoom);

        for (const key of rooms[curRoom]) {
            if (!visited.has(key)) {
                queue.push(key);
                visited.add(key);
            }
        }
    }

    return visited.size === rooms.length;
};

• BFS 로직:
  • 큐에서 현재 방을 빼내고 방문한 것으로 표시합니다.
  • 현재 방에서 얻은 모든 키에 대해, 이미 방문한 방이 아니라면 큐에 추가하고 방문한 것으로 표시
  • 큐가 빌 때까지 반복
• 전체 로직:
  • 0번 방부터 시작하여 BFS를 통해 방문 가능한 모든 방을 체크
  • 최종적으로 visited.size와 rooms.length를 비교하여 모든 방을 방문했는지 여부 반환