leetcode link

Description

There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.

When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.

Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.

---

841. 방과 열쇠

n개의 방이 있고, 방 번호는 0부터 n - 1까지입니다. 모든 방은 잠겨 있고, 오직 방 0만 열려 있습니다. 방을 방문할 때마다, 해당 방에서 새로운 열쇠 세트를 얻을 수 있으며, 이 열쇠들은 다른 방을 열 수 있습니다. rooms[i]에는 방 i를 방문했을 때 얻을 수 있는 열쇠들이 들어 있습니다. 모든 방을 방문할 수 있다면 true, 아니면 false를 반환합니다.

예제 1:

• 입력: rooms = [[1],[2],[3],[]]
• 출력: true
• 설명: 방 0에서 키 1을 얻고, 방 1에서 키 2를 얻으며, 방 2에서 키 3을 얻어 마지막 방을 방문함. 모든 방을 방문했기 때문에 true.

예제 2:

• 입력: rooms = [[1,3],[3,0,1],[2],[0]]
• 출력: false
• 설명: 방 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]의 모든 값은 고유함.

Solution

import java.util.LinkedList;
import java.util.List;

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        boolean[] visited = new boolean[rooms.size()]; // 방문한 방 추적
        List<Integer> keys = new LinkedList<>(); // 획득한 열쇠 목록

        visited[0] = true; // 0번 방 방문 시작
        keys.addAll(rooms.get(0)); // 0번 방의 열쇠 추가

        while (!keys.isEmpty()) {
            int key = keys.remove(0); // 열쇠 사용
            if (visited[key])
                continue; // 이미 방문한 방이면 넘김

            visited[key] = true; // 방 방문 처리
            keys.addAll(rooms.get(key)); // 새 열쇠 추가
        }

        for (boolean v : visited) { // 모든 방 방문 확인
            if (!v)
                return false;
        }
        return true;
    }
}