N개의 방이 있고 방 0에서 시작한다고 가정합니다. 각 방에는 0, 1, 2, ..., N-1에 고유한 숫자가 있으며 각 방은 다음 방에 액세스할 수 있는 몇 가지 키가 있습니다. 즉, 각 방 i에는 키 방[i]의 목록이 있고 각 키 방[i][j]은 [0, 1, ..., N-1]의 정수입니다. 여기서 N =수 방. A key room[i][j] =v, 입력이 [[1], [2], [3], []]이면 숫자 v로 방을 엽니다. 그러면 출력이 true가 됩니다. 기억해야 할 몇 가지 사항이 더 있습니다. −
- 처음에는 모든 방이 잠기 시작합니다(방 0 제외).
- 방 사이를 자유롭게 오갈 수 있습니다.
- 모든 방에 들어갈 수 있는 경우에만 true를 반환해야 합니다.
따라서 우리는 0번 방에서 시작하여 1번 방으로 이동한 다음 1번 방으로 이동하여 2번 방으로, 2번 방에서 열쇠를 받고 3번 방을 방문한 후 모든 방이 방문한 다음 true를 반환합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 빈 대기열을 하나 만들고 모든 방에 대해 방문 배열을 만들고 false로 설정
- queue :=addRooms(객실, 0, 대기열, 방문)
- 방문함[0] :=네
- 큐에 요소가 있는 동안
- queue :=addRooms(객실, 대기열[0], 대기열, 방문)
- 방문함[queue[0]]을 true로 표시,
- 대기열에서 요소 삭제
- 방문한 배열의 모든 요소가 true이면 true를 반환
- addRoom()은 방, 색인, 대기열 및 방문한 배열을 사용합니다. 이것은 다음과 같습니다.
- 객실[색인] 배열의 i용
- 내가 방문하지 않으면 대기열에 i를 삽입합니다.
- 반환 대기열
예제(파이썬)
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
class Solution(object): def canVisitAllRooms(self, rooms): queue = [] visited = [False for i in rooms] queue = self.add_rooms(rooms,0,queue,visited) visited[0] = True while len(queue)>0: queue = self.add_rooms(rooms,queue[0],queue,visited) visited[queue[0]] = True queue.pop(0) return all(visited) def add_rooms(self, rooms,index,queue,visited): for i in rooms[index]: if not visited[i]: queue.append(i) return queue ob1 = Solution() print(ob1.canVisitAllRooms([[1],[2],[3],[]]))
입력
[[1],[2],[3],[]]
출력
true