leetcode 841, Keys and Rooms

문제 설명

0부터 n-1까지 잠긴 방이 있다. 각 방에는 다른 방을 열 수 있는 열쇠 다발이 존재하는데, 이를 이용해서 모든 방을 열 수 있다면 true를, 아니라면 false를 반환하라.
0번째 방은 미리 열어둔다고 가정한다.

문제 풀이

0. 필요한 자료구조
   boolean[] room, 일단 방이 열려있는지 아닌지를 확인하는 배열.
   Stack stack, 각 방에 들어갈 때마다 얻는 열쇠 다발을 저장하는 스택. 여기서 열쇠를 하나씩 빼서 방을 연다.
1. 일단 0번쩨 방은 미리 열어둔다고 했으니, 0번째 방에 먼저 들어간다. 들어간다는 표시로 room[0]를 true로 바꾸고 스택에 0을 넣는다.
2. 스택이 빌 때까지 while문을 돌린다. 스택의 제일 윗 부분에 있는 열쇠를 가지고 와 해당 방문을 열고 그 방에 존재하는 열쇠들의 방에 들어갔다고 표시한 뒤 스택에 넣어준다.
3. while문이 끝났으면 방을 전부 검사하는데, 만일 하나라도 안 들어간 방이 존재한다면 false를 반환하고 아니라면 true를 반환한다.

코드

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

        while(!stack.isEmpty()){
            int current = stack.pop();
            List<Integer> tmp = rooms.get(current);

            for(int i : tmp){
                if(room[i]){
                    continue;
                }else{
                    room[i] = true;
                    stack.add(i);
                }
            }
        }

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

        return true;
    }
}

링크

https://leetcode.com/problems/keys-and-rooms/description/