💡 풀이
var canVisitAllRooms = function (rooms) {
const uniqueKeys = new Set([0]); // 어차피 중복된 키는 소용이 없기 때문에 유일한 값을 저장하기 위해 set을 사용한다.
const stack = [0]; // 0번째 키는 반드시 있기 때문에 0을 넣어준다.
while (stack.length) {
let currentKey = stack.pop(); // stack의 가장 위에 있는 key를 pop해주고
rooms[currentKey].forEach(key => {
if (!uniqueKeys.has(key)) {
// 해당 키가 set에 없던 키라면
uniqueKeys.add(key); // uniqueKeys에도 넣어주고
stack.push(key); // stack에도 넣어준다.
}
});
}
// 결국 uniqueKeys랑 rooms 배열의 길이가 같으면 그게 답이 된다.
return uniqueKeys.size === rooms.length;
};
📝 정리
풀이에 대한 자세한 설명은 주석으로 하였다. 방을 열 수 있는 key는 배열의 index값이기 때문에, 유일한 값들의 집합인 set을 사용하였다. 유일한 값들의 집합인 set과 rooms 배열의 길이가 같다면 rooms 배열의 모든 key가 있다는 뜻이기 때문에 두 값을 비교하면 답을 찾을 수 있다.
수정, 지적을 환영합니다!
문제 링크
https://leetcode.com/problems/keys-and-rooms/
