841. Keys and Rooms

방을 방문하며 방에 놓인 키 꾸러미로 열 수 있는 방을 찾아가라. 모든 방을 방문할 수 있는가 ?

풀이

class Solution {
    boolean isV[];
    int numOfRooms;

    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        
        numOfRooms = rooms.size();
        isV = new boolean[numOfRooms];

        dfs(0, rooms);

        for(boolean b: isV){
           if(!b){
            return false;
           } 
        }

        return true;

    }

    public void dfs(int i, List<List<Integer>> rooms){

        isV[i] = true;
        
        List<Integer> keys = rooms.get(i);
        int numOfKeys = keys.size();

        for(int j=0; j<numOfKeys; j++){
            int key = keys.get(j);
            if(!isV[key]){
                dfs(key ,rooms);
            }
        }
    }
}

결과

후기

• dfs를 가볍게 구상해보기에 좋은 문제인 것 같다.