ABOUT ME

Today
Yesterday
Total
  • LeetCode - 841. Keys and Rooms
    개발/코딩테스트 2023. 8. 25. 14:44

    문제: 841. Keys and Rooms (Medium)

     

    1. 0 부터 n-1 까지 표시된 n 개의 방이 있고, 0번 방을 제외한 모든 방은 잠겨 있음. 모든 방을 방문하려 함.
    2. 방을 방문하면 열쇠를 찾을 수 있고 숫자는 방의 번호를 나타냄.
    2. 모든 방을 방문할 수 있으면 true, 아니면 false 리턴.

     

    예시:

     

    Example 1:
    Input: rooms = [[1],[2],[3],[]]

    Output: true

    Explanation: 0번째 방에서 1번 방의 열쇠를 얻음. 1번 방에서 2번 방의 열쇠를 얻음. 2번 방에서 3번방의 열쇠를 얻음. 3번방까지 모두 방문 할 수 있으므로 true.


    Example 2:
    Input: rooms = [[1,3],[3,0,1],[2],[0]]

    Output: false

    Explanation: 2번 방의 열쇠는 2번방에만 있어서 방문할 수 없으므로 false.

     

     

    풀이:

    class Solution {
        public boolean canVisitAllRooms(List<List<Integer>> rooms) {
            boolean[] visited = new boolean[rooms.size()];
            
            visited[0] = true;
            return visit(0, rooms, visited) == rooms.size();
        }
    
        private int visit(int num, List<List<Integer>> rooms, boolean[] visited) {
            int sum = 1;
            for (Integer i : rooms.get(num)) {
                if (!visited[i]) {
                    visited[i] = true;
                    sum += visit(i, rooms, visited);
                }
            }
            return sum;
        }
    }

     

    설명:

     

    1. visitCount 와 방문 여부를 기록할 visited boolean 배열 선언.

    2. 첫번째 방부터 재귀적으로 방문하며 방문하지 않은 곳은 visited 를 true 로 기록하고 모두 방문.

    3. 최종적으로 visit 에서 리턴되는 값은 방문을 한 count 이며, 해당 count 와 rooms 의 size 를 비교하여 그에 맞게 true, false 리턴.

     

    시간복잡도: O(n)

    공간복잡도: O(n)

     

    Runtime: 0ms Beats 100.00% of users with Java

    Memory: 43.04MB Beats 76.20% of users with Java

     

     


    개인의 해답으로 풀이한 문제입니다. 
    절대적인 정답이 아닐 수 있으며, 더 좋은 개선 방안이 있다면 댓글로 의견 주세요.
Designed by Tistory.