[LeetCode] 841 Keys and Rooms JavaScript

문제 링크

Keys and Rooms - LeetCode

 

문제 유형

그래프, DFS/ BFS

 

문제 풀이

이번 문제는 0 ~ (n - 1)번 방 n개와 각 방에는 번호가 적힌 키가 있다. 키에 적힌 번호는 해당 키로 열 수 있는 방의 번호이다. 0번 방에서부터 모든 방을 열 수 있으면 true를 반환하고, 그렇지 않으면 false를 반환한다.

해당 문제는 그래프 문제로 생각하여 DFS나 BFS를 이용해 그래프를 순회하여 해결 할 수 있다. 각 방을 정점으로 생각하고, 각 방에 있는 키에 적힌 번호에 해당하는 방을 간선으로 연결한다고 생각한다. 그러면 directed graph가 완성된다. iterative DFS 구현을 위해 방문한 노드를 저장할 Set 객체를 생성하고, 인접한 노드를 저장할 stack array를 생성한다. 스택에 모든 원소가 pop 될 때까지 0번 방부터 현재 정점을 pop하고, 정점과 연결된 노드를 visited와 스택에 추가한다. 방의 개수와 방문한 방의 개수가 일치하면 모든 방을 방문한 것으로 간주하여 true가 반환되고, 그렇지 않으면 false가 반환된다. 각 노드를 한번씩 방문하므로 O(n)의 시간 복잡도를 갖는다.

iterative DFS 외에도 recursive DFS, iterative BFS로도 문제를 해결할 수 있다. iterative BFS에서는 queue를 생성하여 각 노드를 push, pop하여 순회한다.

 

코드

// iterative DFS
var canVisitAllRooms = function(rooms) {
    const visited = new Set([0]);
    const stack = [0];
    
    while (stack.length) {
        const keys = rooms[stack.pop()];
        for (let key of keys) {
            if (!visited.has(key)) {
                stack.push(key);
                visited.add(key);
            }
        }
    }
    return rooms.length === visited.size;
};

 

참고

http://youtube.com/watch?v=gl5RhtU2mF8