[LeetCode] 841. Keys and Rooms

📃 문제 설명

(MEDIUM) https://leetcode.com/problems/keys-and-rooms/

• n개의 방이 존재하고 각 방에는 타 방들을 열 수 있는 열쇠들이 존재할 때, 0번 방만이 열려 있을 때 모든 방들에 대한 방문이 가능한지를 물어보는 문제이다.

🔎 문제 접근

• BFS로 접근하되, 해당 방을 여러 번 접근하지 않도록 is_visited 라는 변수를 통해 체크해주었다.
• 다음에 visit할 방의 목록은 queue를 통해 관리해주었다.
• 답 출력 속도를 빨리 하기 위해, 아직 방문하지 않은 방들의 갯수를 세는 visited_left 변수를 만들어, 해당 변수가 0일 때 True, 아닐 때 False를 출력하도록 작성해주었다.

✨ 문제 풀이

from collections import deque

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        N = len(rooms)
        is_visited = [False] * N
        is_visited[0] = True #0번 방은 곧 들릴 예정
        visited_left = N - 1 #0번 방 제외 다른 방들은 들리지 않음
        q = deque([0]) #0번 방을 가장 처음으로 들릴 queue 제작
        
        #들릴 방이 남아 있을 때까지 반복, 이미 모든 방 방문했으면 break
        while len(q) and visited_left:
            now = q.popleft()
            #현재 방에서 들릴 수 있는 다음 방들에 대해 is_visited 체크
            for key in rooms[now]:
                if not is_visited[key]:
                    is_visited[key] = True
                    visited_left -= 1
                    q.append(key)
        
        return False if visited_left else True

• Runtime과 Memory Usage가 모두 준수하다. 개선 가능한 방법이 생각나지는 않는다.