[leetcode 841. Keys and Rooms 열쇠의 방] - DFS

문제

에서 n으로 표시된 방이 있으며  방을 제외한 모든 방은 잠겨 있습니다 . 당신의 목표는 모든 방을 방문하는 것입니다. 그러나 열쇠가 없으면 잠긴 방에 들어갈 수 없습니다.0n - 10

방을 방문하면 그 방에서 고유한 열쇠 세트를 찾을 수 있습니다 . 각 열쇠에는 어느 방의 잠금이 해제되는지 나타내는 숫자가 있으며, 이 열쇠를 모두 가져가면 다른 방의 잠금을 해제할 수 있습니다.

room을 방문했을 때 얻을 수 있는 키 세트가 있는 배열이 주어지면 rooms모든 방 을 방문할 수 있으면 반환 하고 그렇지 않으면 반환합니다 .rooms[i]itrue false

 

예시 1:

입력: Rooms = [[1],[2],[3],[]]

 출력: true

 설명:  

방 0을 방문하여 키 1을 가져왔습니다. 

그런 다음 방 1을 방문하여 키 2를 가져왔습니다. 

그런 다음 방을 방문합니다. 2 그리고 열쇠 ​​3을 집습니다. 

그런 다음 방 3을 방문합니다 

. 모든 방을 방문할 수 있었으므로 true를 반환합니다.

예 2:

입력: Rooms = [[1,3],[3,0,1],[2],[0]]

 출력: false

 설명: 방을 잠금 해제하는 유일한 열쇠가 방 번호 2에 있기 때문에 방 번호 2에 들어갈 수 없습니다. .

 

제약:

• n == rooms.length
• 2 <= n <= 1000
• 0 <= rooms[i].length <= 1000
• 1 <= sum(rooms[i].length) <= 3000
• 0 <= rooms[i][j] < n
• 의 모든 값은 고유rooms[i] 합니다 .

코드

import java.util.List;
class Solution {
    boolean[] visited;
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        //1.자료구조 초기화
        visited = new boolean[rooms.size()];
        //2.dfs
        dfs(0, rooms);
        // 방문체크한 거 체크해서 return
        for(int i=0; i<visited.length;i++){
            if(visited[i] == false){
                return false;
            }
        }
        return true;
    }
    public void dfs(int start, List<List<Integer>> rooms){
        //3.종료조건 -> 없음 rooms 파라미터만 체크 하고 끝내면됨
        //3.방문여부처리 및 재귀
        visited[start] = true;
        List<Integer> list = rooms.get(start);
        for(int key : list){
            if(!visited[key]){
                dfs(key, rooms);
            }
        }
    }
}