리스트의 리스트로 구성된 rooms가 주어졌다고 가정해 봅시다. 각 인덱스 i는 하나의 방을 나타내며, rooms[i]에는 다른 방을 열 수 있는 열쇠들이 담겨 있습니다. 0번 방은 처음부터 열려 있고 우리는 그 방에서 시작하며, 나머지 방들은 모두 잠겨 있습니다. 열린 방 사이는 자유롭게 이동할 수 있을 때, 모든 방을 열 수 있는지 확인해야 합니다.
예를 들어 입력이 rooms = [[2, 0], [3], [1], []]라면 결과는 True입니다. 0번 방에서 시작해 열쇠 2번으로 2번 방에 들어가고, 2번 방의 열쇠로 1번 방을 연 뒤, 마지막으로 3번 방의 열쇠를 얻어 모든 방을 열 수 있기 때문입니다.
이 문제는 본질적으로 그래프 순회(DFS/BFS) 문제입니다. 각 방을 노드로, 열쇠를 간선으로 생각하면 0번 방에서 도달 가능한 모든 방의 개수가 전체 방의 개수와 같은지 확인하면 됩니다. 해결 절차는 다음과 같습니다.
- n := rooms의 크기(전체 방의 개수)
- ready := 0만 담고 있는 리스트(방문 대기열 역할)
- seen := 방문한 방을 기록하는 새로운 집합
- ready가 비어 있지 않은 동안 반복:
- u := ready의 마지막 요소를 꺼냄(pop)
- u를 seen에 추가하여 방문 처리
- rooms[u]에 있는 각 열쇠 v에 대해:
- v가 아직 seen에 없다면 ready의 끝에 추가
- seen의 크기가 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
동작 원리 정리
위 코드에서 ready.pop()은 리스트의 마지막 요소를 꺼내므로 깊이 우선 탐색(DFS)처럼 동작합니다. 만약 ready.pop(0)을 사용해 앞에서 요소를 꺼내면 너비 우선 탐색(BFS)이 되며, 결과는 동일하게 얻을 수 있습니다. 시간 복잡도는 방과 열쇠를 각각 한 번씩만 처리하므로 O(N + K)(N은 방의 개수, K는 열쇠의 총 개수)이며, 공간 복잡도는 O(N)입니다.