841. 열쇠와 방(자바스크립트 솔루션)

설명:

N 개의 방이 있으며 방 0에서 시작합니다. 각 방에는 0, 1, 2, ..., N-1의 고유 번호가 있으며 각 방에는 다음 방에 액세스할 수 있는 몇 가지 키가 있을 수 있습니다.

공식적으로 각 방 i는 키 방[i]의 목록을 가지며 각 키 방[i][j]은 [0, 1, ..., N-1]의 정수입니다. 여기서 N = rooms.length입니다. A key room[i][j] = v는 숫자 v로 방을 엽니다.

처음에는 모든 방이 잠기 시작합니다(방 0 제외).

방 사이를 자유롭게 왔다갔다 할 수 있습니다.

모든 방에 들어갈 수 있는 경우에만 true를 반환합니다.

해결책:

시간 복잡도 : O(n)
공간 복잡도: O(n)

// DFS apprach
var canVisitAllRooms = function(rooms) {
    // Keep track of visited rooms
    const set = new Set();

    // Recursive dfs function to search rooms
    function dfs(index, rooms, set) {
        // Don't check this room if it has already been visited
        if(set.has(index)) return;
        // Add this room to the list of checked rooms
        set.add(index);
        // Check all the keys in this room
        for(const key of rooms[index]) {
            dfs(key, rooms, set);
        }
    }
    // Start at the first room
    dfs(0, rooms, set);

    // Check if all the rooms have been visited
    return set.size === rooms.length;
};