LeetCode - 841. Keys and Rooms

[LeetCode] 841. Keys and Rooms

LeetCode 841번 문제를 풀어보았다.. Link

Problem

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.

Intuition

그래프의 한 노드에서 시작하여 다른 노드로 도달할 수 있는지 확인하는 Graph Traversal Problem 문제 유형.

Breadth-First Search나 Depth-First Search 알고리즘을 활용하여 풀 수 있다.

Approach

내가 여지껏 접한 그래프 문제는 보통 리스트나 딕셔너리로 그래프를 구현해놓고 그 그래프안에서 서치해나가는 방법으로 푸는 경우가 많았다.

1. 그래프를 딕셔너리로 구현한다.
2. 반복 방지를 위해 해당 노드를 방문했는지에 대한 Bool type array visit을 만든다.
3. Queue를 생성하고 출발지점 0을 추가한다.
4. 모든 Room을 방문했다면 visit의 sum이 room의 개수와 같아지기 때문에 같다면 True를 반환한다.
5. 아니라면 Queue에서 방을 하나 pop하고, 그 방에 있는 방문하지 않은 다른 방 열쇠가 있다면 Queue에 append한다.
6. Queue가 빌 때까지 4-5를 반복하고, 반복이 종료되면 False를 반환한다.

Complexity

• Time complexity:

  시간복잡도는 방개수를 R, 열쇠개수를 K라고 할 때 BFS썼기 때문에 \(O(R+K)\)

• Space complexity: \(O(R+K)\)

My Code

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        """
        Goal: visit all the rooms
        """
        key_book = {}
        for idx, keys in enumerate(rooms):
            key_book[idx] = keys

        visit = [True] + [False] * (len(rooms) - 1)
        queue = [0]

        while queue:
            if sum(visit) == len(rooms):
                return True
            current = queue.pop(0)
            keys = key_book[current]

            for key in keys:
                if not visit[key]:
                    visit[key] = True
                    queue.append(key)

        return False

지금보니까 굳이 Dictionary로 만들어서 풀 필요는 없었던거 같다.

애초에 Rooms에 방 순서대로 방안에 있는 다른 방 키가 정의되어있기 때문에 Dictionary 생성을 생략하고 Rooms를 사용해도 같다.

-> 공간복잡도를 \(O(R)\)로 줄일 수 있음.