LeetCode 841. Keys and Rooms

Graph Theory 문제 3번
https://leetcode.com/problems/keys-and-rooms/

나의 풀이(0ms, 100.00%)

BFS

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        unlocked = [False] * len(rooms)
        unlocked[0] = True

        q = collections.deque(rooms[0])
        while q:
            room = q.popleft()
            unlocked[room] = True
            for key in rooms[room]:
                if unlocked[key] is False:
                    q.append(key)
        
        if False in unlocked:
            return False
        return True

나의 풀이 개선

BFS

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        unlocked = [False] * len(rooms)
        unlocked[0] = True

        q = deque([0])
        while q:
            room = q.popleft()
            for key in rooms[room]:
                if not unlocked[key]:
                    unlocked[key] = True
                    q.append(key)
        
        return all(unlocked)

다른 풀이1(0ms, 100.00%)

DFS, recursive

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        visited = set()

        def dfs(room):
            visited.add(room)
            for key in rooms[room]:
                if key not in visited:
                    dfs(key)

        dfs(0)
        return len(visited) == len(rooms)

다른 풀이2(0ms, 100.00%)

DFS, stack

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        visited = set()
        stack = [0]

        while stack:
            room = stack.pop()
            if room not in visited:
                visited.add(room)
                stack.extend(rooms[room])
        
        return len(visited) == len(rooms)