[LeetCode] 841 Keys and Rooms JavaScript
문제 링크
Keys and Rooms - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
문제 유형
그래프, 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;
};