841. Keys and Rooms

Keys and Rooms - LeetCode

0부터 n - 1까지 레이블이 붙은 n개의 방이 있고, 모든 방은 잠겨 있습니다. 단, 0번 방은 잠기지 않았습니다. 목표는 모든 방을 방문하는 것입니다. 그러나 방문하지 않은 방의 열쇠 없이 잠긴 방에 들어갈 수 없습니다.
방을 방문하면 해당 방에 있는 서로 다른 열쇠 세트를 발견할 수 있습니다. 각 열쇠에는 어떤 방을 열 수 있는 번호가 표시되며, 여기서 열쇠를 가져와 다른 방을 열 수 있습니다.
rooms라는 배열이 주어집니다. rooms[i]는 방 i를 방문하면 얻을 수 있는 열쇠 세트를 나타냅니다. 모든 방을 방문할 수 있는 경우 true를, 그렇지 않으면 false를 반환합니다.

 

There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.

When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.

Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.

 

Example 1:

Input: rooms = [[1],[2],[3],[]]
Output: true
Explanation: 
We visit room 0 and pick up key 1.
We then visit room 1 and pick up key 2.
We then visit room 2 and pick up key 3.
We then visit room 3.
Since we were able to visit every room, we return true.

Example 2:

Input: rooms = [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can not enter room number 2 since the only key that unlocks it is in that room.

문제 요약:

0번 방을 시작으로 주어진 열쇠를 사용하여 모든 방을 방문할 수 있는지 확인하는 문제입니다.

 

풀이과정 설명:

Queue 를 이용하여 방 키를 등록하고, 해당 키로 방문 가능한 방을 HashSet 에 등록한다.

Queue Add 로 이미 방문했던 방 여부 확인하고, 방문 하지 않은 방이면 key 를 방문

Queue 가 종료된 시점에 방문가능한 방 HashSet 갯수와 룸 갯수 체크하여 반환

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        Set<Integer> setKey = new HashSet<>();
        
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        while(!queue.isEmpty()){
            int _room = queue.poll();

            if(setKey.add(_room)){
                List<Integer> _keys = rooms.get(_room);

                for(Integer key : _keys){
                    queue.add(key);
                }
            }
        }
        return (rooms.size() == setKey.size());
    }
}

 

룸 방문 여부를 HashSet 로 관리했떠니 느리다...

속도 개선을 위해 배열을 사용해보자

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        boolean[] visitRoom = new boolean[rooms.size()];
        visitRoom[0] = true;

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);

        while (!queue.isEmpty()) {
            int keys = queue.poll();
            for (int _key : rooms.get(keys)) {
                if (!visitRoom[_key]) {
                    visitRoom[_key] = true;
                    queue.offer(_key);
                }
            }
        }

        for (boolean visited : visitRoom) {
            if (!visited) {
                return false;
            }
        }

        return true;
    }
}