문제 설명
N개의 방이 있고, 우리는 0번 방에서 시작한다고 가정해 봅시다. 각 방에는 0부터 N-1까지 서로 다른 번호가 매겨져 있으며, 각 방 안에는 다른 방을 열 수 있는 열쇠가 몇 개 들어 있을 수 있습니다. 즉, 각 방 i는 rooms[i]라는 열쇠 목록을 가지고 있고, 각 열쇠 rooms[i][j]는 0부터 N-1 사이의 정수입니다(여기서 N은 방의 총 개수). 만약 rooms[i][j] = v라면, 그 열쇠로 v번 방을 열 수 있습니다.
예를 들어 입력이 [[1], [2], [3], []]이라면 출력은 true가 됩니다.
문제의 핵심 조건
- 처음에는 0번 방을 제외한 모든 방이 잠겨 있습니다.
- 방과 방 사이를 자유롭게 오갈 수 있습니다.
- 모든 방에 들어갈 수 있는 경우에만 true를 반환해야 합니다.
동작 과정을 살펴보면, 0번 방에서 시작해 열쇠 1을 얻고 1번 방으로 이동합니다. 1번 방에서 2번 방의 열쇠를 얻고, 2번 방에서 3번 방의 열쇠를 얻습니다. 3번 방까지 모두 방문한 뒤 전체 방을 확인했을 때 모든 방을 방문했다면 true를 반환하면 됩니다.
해결 접근 방법
이 문제는 너비 우선 탐색(BFS)을 활용해 해결할 수 있습니다. 큐(queue)와 방문 여부를 기록하는 visited 배열을 사용하는 구체적인 단계는 다음과 같습니다.
- 빈 큐를 하나 만들고, 모든 방에 대한 visited 배열을 False로 초기화합니다.
- add_rooms() 함수를 호출해 0번 방의 열쇠들을 큐에 추가하고, visited[0]을 True로 설정합니다.
- 큐에 요소가 남아 있는 동안 다음을 반복합니다.
- 큐의 맨 앞 방이 가진 열쇠들을 add_rooms()로 큐에 추가합니다.
- 해당 방을 visited에서 True로 표시합니다.
- 큐에서 맨 앞 요소를 제거합니다.
- 반복이 끝난 후 visited 배열의 모든 값이 True라면 true를 반환합니다.
add_rooms() 함수의 역할
add_rooms() 함수는 rooms, index, queue, visited 배열을 인자로 받아 다음과 같이 동작합니다.
- rooms[index] 배열의 각 열쇠 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
정리
'키와 방' 문제는 그래프 탐색의 대표적인 유형으로, BFS와 큐를 활용하면 깔끔하게 해결할 수 있습니다. 시간 복잡도는 O(N + K)입니다(N은 방의 수, K는 열쇠의 총 개수). 방문 여부를 반드시 체크해 같은 방을 중복해서 큐에 넣지 않도록 하는 것이 핵심 포인트입니다.