[LeetCode] 841. Keys and Rooms (java)

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

 

 

문제 파악

0부터 n-1까지 번호가 매겨진 n개의 방이 있으며, 0번 방을 제외한 모든 방은 잠겨 있다.

입력으로 주어지는 배열 rooms에서 rooms[i]는 i번 방을 방문했을 때 얻을 수 있는 키들의 집합을 의미한다.

이 키들을 사용하여 모든 방을 열고 방문할 수 있는지 여부를 return하라.

 

 

문제 풀이

• BFS
• DFS

BFS

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[rooms.size()];

        visited[0] = true;
        queue.add(0);

        while (!queue.isEmpty()) {
            int i = queue.remove();
            for (int key : rooms.get(i)) {
                if (!visited[key]) {
                    visited[key] = true;
                    queue.add(key);
                }
            }
        }

        for (boolean v : visited) {
            if (!v) return false;
        }

        return true;
    }
}

 

📊 실행 결과

 

DFS

class Solution {
    boolean[] visited;

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

        dfs(0, rooms);

        for (boolean v : visited) {
            if (!v) return false;
        }    

        return true;
    }

    void dfs(int i, List<List<Integer>> rooms) {
        visited[i] = true;
        for (int key : rooms.get(i)) {
            if (!visited[key]) {
                dfs(key, rooms);
            }
        }
    }
}

 

📊 실행 결과