[Graph - DFS, Medium] Keys and Rooms

https://leetcode.com/problems/keys-and-rooms/description/?envType=study-plan-v2&envId=leetcode-75

DFS 문제인데, 뻗어나갈 수 있는 조건이 rooms.get(current)안에 들어있다고 보면 되겠다.

일단 모든 방을 갔는지 체크하는 boolean[] visited를 만들어 두고, 순회하면서 세팅한다.

정답조건은 visited의 모든 원소가 true인지 판단하면 알 수 있겠다.

DFS 로직은 간단하다.

• visited[current]면 더 진행하지 않음
• 온 적 없는 방이면 visited[current] = true, 키를 얻어(rooms.get(current))서 다음 재귀에 해당 방 번호로 사용

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

        dfs(rooms, visited, 0);

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

    private void dfs(List<List<Integer>> rooms, boolean[] visited, int currentRoom) {
        if (visited[currentRoom]) {
            return;
        }

        visited[currentRoom] = true;
        for (int key : rooms.get(currentRoom)) {
            dfs(rooms, visited, key);
        }
    }
}