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

📜문제 내용

0부터 n-1까지의 번호가 있는 n개의 방들이 있고, 모든 방들은 0번 방을 제외하고 모두 잠겨있다.
너의 목표는 모든 방들을 방문하는 것이다. 하지만, 당신은 방에 해당되는 열쇠 없이는 잠긴 방에 들어갈 수 없다.

방에 방문할 때, 당신은 그곳에서 구별되는 열쇠들을 찾을 수 있다. 각각의 열쇠들은 방을 열 수 있는 번호들이 적혀있고, 당신은 다른 방들을 열 수 있는 그것들을 모두 가져갈 수도 있다.

i번째 방에 방문하면 열쇠 세트를 얻을 수 있는 방들이 배열로 주어졌을 때, 모든 방들을 방문할 수 있으면 true를, 그렇지 않으면 false를 리턴하라.

🚧제약 조건
1. n == rooms.length
2. 2 <= n <= 1000
3. 0 <= rooms[i].length <= 1000
=> 1000 * 1000 = 10^6 < 10^8이므로 brute-force 가능
4. 1 <= sum(rooms[i].length) <= 3000
=> 적어도 1번 이상의 열쇠는 있다는 의미
5. 0 <= rooms[i][j] < n
=> 0부터 n-1까지의 번호
6. rooms[i]의 모든 값들은 unique하다.(중복되는 value가 없다는 의미)

🧐문제 해석

0번방을 제외하고 모두 잠겨있다 -> rooms[0][0]부터 방문하라는 의미
모든 방들을 방문 -> bfs 또는 dfs로 모든 정점을 방문해라
각각의 열쇠들은 방을 열 수 있는 번호 -> 방향이 있는 Directed graph라는 의미
방들을 방문할 때 distinct keys들을 얻을 수 있음 -> 번호가 적혀있는 해당 정점에 방문할 수 있음

🔑Rooms는 Vertex를, Keys는 Edge를 의미한다.
👉따라서 이 문제는 "인접 리스트로 주어졌을 때, 해당 input을 bfs 또는 dfs로 모두 방문할 수 있는지"를 묻는 문제로 해석될 수 있다.

bfs 풀이

⚙️코드 설계

별다른 건 없고, 인접 리스트의 코드 템플릿을 그대로 적용한다.

💻코드 구현

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

        // bfs 탐색
        // queue: keys(Edge)들을 추가하기 위한 자료구조
        Queue<List<Integer>> q = new LinkedList<>();
        visited[0] = true; // 0번방은 무조건 방문
        q.offer(rooms.getFirst());

        while (!q.isEmpty()) {
            List<Integer> keys = q.poll();

            for (Integer key : keys) {
                if (!visited[key]) {
                    visited[key] = true;
                    q.offer(rooms.get(key)); // key에 해당하는 room에 들어가서 distinct keys를 얻음

                }
            }
        }

        // 하나라도 방문을 안 했으면 false를 리턴
        for (boolean v : visited) {
            if (!v) {
                return false;
            }
        }

        return true;

    }

}

• 💡원래 bfs 코드에는 q.offer(v)로 String 또는 Integer 타입만 추가를 했었는데, 이 문제에서는 큐에 추가되는 keys들이 List<Integer> 타입이므로, 2차원 리스트의 rooms에서 key(index)에 해당하는 keys를 큐에 추가하면 된다.

dfs 풀이

💻코드 구현

public class KeysAndRoomsSolution {

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

        // 0번방을 무조건 먼저 방문해야 하기 때문에 사전 세팅
        // dfs 탐색
        visited[0] = true;
        List<Integer> keys = rooms.get(0);

        for (Integer key : keys) {
            if (!visited[key]) {
                dfs(key, visited, rooms);
            }
        }

        // 하나라도 방문을 안 했으면 false를 리턴
        for (boolean v : visited) {
            if (!v) {
                return false;
            }
        }

        return true;

    }

    private static void dfs(Integer key, boolean[] visited, List<List<Integer>> rooms) {
        visited[key] = true;
        List<Integer> keys = rooms.get(key);

        for (Integer k : keys) {
            if (!visited[k]) {
                dfs(k, visited, rooms);
            }
        }

    }

}

• 0번방으로 가서 key들을 얻고, 해당 key에 해당하는 방을 방문하지 않았으면 dfs를 호출한다.
  • 🤩dfs 함수 정의 부분은 dfs 함수 템플릿을 그대로 사용했는데, keys를 순회하기 위해 rooms를 dfs의 파라미터로 전달해서 List<Integer> keys = rooms.get(key);로 가져온 생각을 위의 bfs 코드 중 큐에 추가하는 아이디어를 활용해서 구현하였다.

⏰rooms는 정점이고, keys는 간선이므로, bfs, dfs 모두 $O(V+E)$의 시간복잡도를 가진다.