방이라는 목록 목록이 있다고 가정합니다. 방의 각 인덱스 i는 방을 나타내고 rooms[i]는 다른 방을 여는 다른 키를 나타냅니다. 방 0이 열려 있고 우리는 그 방에 있고 다른 모든 방은 잠겨 있습니다. 열린 방 사이를 자유롭게 이동할 수 있습니다. 모든 방을 열 수 있는지 여부를 확인해야 합니다.
따라서 입력이 rooms =[[2, 0], [3],[1],[]]와 같으면 출력은 True가 됩니다. 우리가 방 0에서 시작하여 키를 사용하여 방 2로 갈 수 있기 때문입니다. 2. 2번 방에서 1번 방으로 갈 수 있습니다. 그런 다음 3번 방의 키를 가져 와서 엽니다. 모든 것이 열려 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다.
- n :=방 크기
- ready :=단일 요소가 0인 목록
- 본 :=새로운 세트
- 준비가 비어 있지 않은 동안 수행
- u :=ready의 마지막 요소 및 ready에서 삭제
- 본 것으로 표시
- 객실[u]의 각 v에 대해 다음을 수행합니다.
- v가 보이지 않으면
- 준비 끝 부분에 v 삽입
- v가 보이지 않으면
- 본 크기가 n과 같으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
예시
class Solution: def solve(self, rooms): n = len(rooms) ready = [0] seen = set() while ready: u = ready.pop() seen.add(u) for v in rooms[u]: if v not in seen: ready.append(v) return len(seen) == n ob = Solution() rooms = [ [2, 0], [3], [1], [] ] print(ob.solve(rooms))
입력
rooms = [[2, 0],[3],[1],[]]
출력
True