Keys and Rooms

#programming #java #beginners #basic

Given:
There are rooms marked from 0 to n-1. Room 0 is the only room which is unlocked. Goal is to see whether all the rooms are visited or not and accordingly return the boolean value.

This is a typical BFS graph problem.

Approach :

When it's a BFS, we make use of Queue data structure.
'visited array' to keep track of which nodes are visited
Traverse to check whether all the nodes are visited or not. If not, return false. Else, return true.

Algorithm :

Start with room 0 which is add 0 to the queue and mark visited[0] = 1
Now until the queue is empty
- take the node from the queue
- Get the adjacent nodes of the "node" and add it to the queue and mark it as visited.
Traverse the visited array to check whether all the nodes are visited or not.

Code:

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {

        int n = rooms.size();

        int visited[] = new int[n];

        Queue<Integer> queue = new LinkedList<>();

        visited[0] = 1;

        queue.add(0);

        while(!queue.isEmpty()){
            int node = queue.remove();

            for(int adj : rooms.get(node)){
                if(visited[adj]==0){
                    visited[adj] = 1;
                    queue.add(adj);
                }
            }
        }

        for(int visit : visited){
            if(visit==0)
            return false;
        }

        return true;
    }
}