.leetcode(841. Keys and Rooms)

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

 

1. 2022.01.30 시도

소요시간: 11분(3분 구상, 8분 코딩, recursive), 4분(앞서 구상, 4분 코딩, iterative)

// recursive
class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        if (rooms == null || rooms.size() == 0) {
            return true;
        }
        int roomSize = rooms.size();
        boolean[] visited = new boolean[roomSize];
        
        
        openDoor(0, rooms, visited);
               
        int counter =0;
        for (int i=0; i<visited.length; i++) {
            if (visited[i] == true) counter++;
        }
        
        return counter == roomSize;
    }
    
    public void openDoor(int index, List<List<Integer>> rooms, boolean[] visited) {
        if (visited[index]) {
            return;
        }
        
        visited[index] = true;
        List<Integer> keys = rooms.get(index);
        for (int key: keys) {
            openDoor(key, rooms, visited);
        }
    }
}

// iterative
class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        if (rooms == null || rooms.size() == 0) {
            return true;
        }
        int roomSize = rooms.size();
        boolean[] visited = new boolean[roomSize];
        
        LinkedList<List<Integer>> stack = new LinkedList<>();
        stack.push(rooms.get(0));
        visited[0] = true;
        while (!stack.isEmpty()) {
            List<Integer> keys = stack.pop();
            for (int key: keys) {
                if (visited[key] == true) {
                    continue;
                }
                visited[key] = true;
                stack.push(rooms.get(key));
            }
        }
        
               
        int counter =0;
        for (int i=0; i<visited.length; i++) {
            if (visited[i] == true) counter++;
        }
        
        return counter == roomSize;
    }
}

풀이 접근 과정

조건을 보니 범위가 제한적이다. 이건 array를 룸 갯수만큼 생성해서 사용하면 편하겠구나 생각했다. 이때 만들 array는 방문여부다. 방문여부를 boolean[]로 생성하되 최대 1000개이니 그것에 맞춰 만들어야겠다.

boolean[] visited으로 체크하면 O(n)으로 찾아낼 수 있겠다. 싶었다.

 

느낀점

• 문제 유형을 뭐라할지 모르겠으나 방문여부만 체크하면 사실 기존의 문제유형들과 다르지 않았다.
• 실제로 TimeComplexity는 O(N+E)이다. N은 룸의 갯수이고 E는 키의 갯수다.

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형