Keys and Rooms

Keys and Rooms - LeetCode

접근 방법 [필수 작성]

제한 조건 확인

n 은 최대 1000

방길이 최대 n 개

각 방에 있을 수 있는 키 갯수 n개

전체방의 키 갯수는 3n 개

아이디어

큐로 BFS 구현

0번방에 갔을때, 나오는키에 맞는 방먼저 탐색 → BFS 탐색

모든 BFS 탐색 끝났는데

아직 visited 안된 room 이 한개라도 존재하면 False

모든 방 다 visited 면 True

시간복잡도

O(n^2) 이기는 한데 사실상 BFS 여서 탐색 더 할 필요없는 것도 있을고,

전체방의 키 갯수는 3n 개로 제한이 있기 때문에 N^2 보다 훨씬 적을 것임.

자료구조

visited[bool] → 특정 방번호에 방문했었는지 안했었는지

코드 구현 [필수 작성]

from collections import deque

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        next_room_num = deque([0])
        visited = [False for _ in range(len(rooms))]
        #print(next_room_num.popleft())
        #print(visited)

        while next_room_num:
            #print("deque: ", next_room_num)
            next_room = next_room_num.popleft()
            #print(next_room)
            if not visited[next_room]:
                visited[next_room] = True
                #print(visited)
                for nr in rooms[next_room]:
                    #print(nr)
                    next_room_num.append(nr)

        for visit in visited:
            if visit == False:
                return False
        
        return True

배우게 된 점 [ 필수 X ]

visited_1 = [False for _ in range(len(rooms))]
visited_2 = [[False] for _ in range(len(rooms))]
visited_3 = [False * 3]
visited_4 = [[False] * 3]
visited_5 = [False] * 3

list comprehension 방법 말고, 곱하기를 활용한 직관적인 방법을 활용해서 [False,False,False] 를 만드는 방법

질문 [ 필수 X ]

피드백 [ 코치 작성 ]

수고하셨습니다!