열쇠 와 방

841. 열쇠 와 방
N 개의 방 이 있 습 니 다. 처음에 당신 은 0 번 방 에 있 었 습 니 다.방 마다 번호 가 다 릅 니 다. 0, 1, 2,..., N - 1, 그리고 방 안에 다음 방 으로 들 어 갈 수 있 는 열쇠 가 있 을 수 있 습 니 다.형식적 으로 각 방 i 에 대해 하나의 열쇠 목록 이 있 습 니 다. rooms [i], 각 열쇠 rooms [i] [j] 는 [0, 1,..., N - 1] 중의 정수 로 표시 되 는데 그 중에서 N = rooms. length 입 니 다.열쇠 룸 [i] [j] = v 번호 가 v 인 방 을 열 수 있 습 니 다.
처음에는 0 호실 을 제외 한 나머지 모든 방 이 잠 겨 있 었 다.
너 는 자 유 롭 게 방 사 이 를 왔다갔다 할 수 있다.
각 방 에 들 어가 서 트 루 로 돌아 갈 수 있다 면, 그렇지 않 으 면 false 로 돌아 갑 니 다.
예시 1:
입력: [1], [2], [3], [] 출력: true 설명: 우 리 는 0 호실 부터 열 쇠 를 받 습 니 다.그 후에 우 리 는 1 호실 에 가서 열쇠 2 를 받 았 다.그리고 우 리 는 2 호실 에 가서 열 쇠 를 받 았 다.결국 우 리 는 3 호실 로 갔다.우 리 는 모든 방 에 들 어 갈 수 있 기 때문에, 우 리 는 true 로 돌아간다.예시 2:
입력: [1, 3], [3, 0, 1], [2], [0] 출력: false 설명: 우 리 는 2 호실 에 들 어 갈 수 없습니다.문제 풀이: 1) 광 검색 대기 열 2) 깊이 재 귀적 으로 방향 도 (인접 표) 를 정 하고 0 번 노드 에서 출발 하여 모든 노드 에 도착 할 수 있 는 지 물 어 봅 니 다.0 에서 출발 하여 스 트 리밍 그림 을 넓 은 범위 로 우선 검색 합 니 다.보조 대기 열 과 접근 표지 배열 sloution: 1) 검색

class Solution {
     
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
     
   boolean[] visit=new boolean[rooms.size()];
        Queue<Integer> queue=new LinkedList<>();
        List<Integer> list=rooms.get(0);
        for (int i = 0; i <list.size() ; i++) {
     
            queue.offer(list.get(i));
        }
        visit[0]=true;
        while (true){
     
            int tmp=0;
            if (!queue.isEmpty()){
     
                tmp=queue.poll();
            }else break;
            if (visit[tmp]) continue;
            List<Integer> list1=rooms.get(tmp);
            for (int i = 0; i <list1.size(); i++) {
     
                if (!visit[list1.get(i)]){
     
                    queue.offer(list1.get(i));
                }
            }
            visit[tmp]=true;
        }
        for (int i = 0; i < visit.length; i++) {
     
            if (!visit[i]){
     
                return false;
            }
        }
        return true;
    }
}

class Solution {
     
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
     
    int n=rooms.size(),num=0;
    boolean[]vis =new boolean[n];
    Queue<Integer> que=new LinkedList<Integer>();
    vis[0]=true;
    que.offer(0);

    while(!que.isEmpty()){
     
        int x=que.poll();
        num++;
        for(int it:rooms.get(x)){
     
            if(!vis[it]){
     
                vis[it]=true;
                que.offer(it);
            }
        }
    }
    return num==n;
    }
}

2) 관 해 깊이

class Solution {
     
    boolean[] vis;
    int num;

    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
     
        int n = rooms.size();
        num = 0;
        vis = new boolean[n];
        dfs(rooms, 0);
        return num == n;
    }

    public void dfs(List<List<Integer>> rooms, int x) {
     
        vis[x] = true;
        num++;
        for (int it : rooms.get(x)) {
     
            if (!vis[it]) {
     
                dfs(rooms, it);
            }
        }
    }
}