[LeetCode] 841. Keys and Rooms

말하는 감자·2024년 11월 18일

BFS DFS Graph leetcode python 그래프 리트코드 코딩테스트 코딩테스트 준비 파이썬

LeetCode

목록 보기

11/32

이번 문제는 그래프 순회 BFS, DFS을 한 번에 떠오르기 힘든 문제입니다. 한 번 살펴볼까요?

1. 오늘의 학습 키워드

Graph
DFS
BFS

2. 문제: 841. Keys and Rooms

단계: Medium
주제: Depth-First Search, Breadth-First Search, Graph
출처: https://leetcode.com/problems/keys-and-rooms/description/

Description

There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.

When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.

Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.

Example 1:

Input: rooms = [[1],[2],[3],[]]
Output: true
Explanation:
We visit room 0 and pick up key 1.
We then visit room 1 and pick up key 2.
We then visit room 2 and pick up key 3.
We then visit room 3.
Since we were able to visit every room, we return true.

Example 2:

Input: rooms = [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can not enter room number 2 since the only key that unlocks it is in that room.

Constraints:

n == rooms.length
2 <= n <= 1000
0 <= rooms[i].length <= 1000
1 <= sum(rooms[i].length) <= 3000
0 <= rooms[i][j] < n
All the values of rooms[i] are unique.

3. 문제 풀이

0번방부터 n-1번방까지 총 n개의 방이 있습니다. 0 번 방을 제외한 모든 방은 잠겨 있습니다. 우리의 목표는 모든 방에 방문하는 것입니다. 하지만 잠겨져 있는 방은 key가 없으면 방문을 할 수가 없습니다. 각 방에 방문할 때, 별개의 열쇠 뭉치를 찾을 수도 있습니다. 각각의 열쇠에는 Number가 쓰여져 있고, 해당 번호에 해당하는 방을 잠금 해제할 수 있습니다. 열쇠뭉치는 모두 가져갈 수 있고, 언제든 방문을 열기 위해 사용할 수 있습니다.

문제에서 rooms 배열이 주어지고, rooms[i]는 해당 방에서 얻을 수 있는 열쇠뭉치 목록을 표현합니다. 모든 방을 방문할 수 있다면 True, 그렇지 않으면 False를 반환하는 문제입니다.

모든 방을 방문할 수 있다면 True, 그렇지 않으면 False를 반환한다는 것은 모든 방을 순회? 한다고 볼 수 있습니다. 그렇기 때문에 BFS, DFS를 어렴풋이 떠오를 수 있습니다. 하지만 아직 확실하지 않은 상황입니다. 순서대로 나아가보죠!

Step1. 문제 이해하기

우선, input과 output을 제약조건과 함께 확인해보겠습니다.

Input:
- 방의 길이는 n, n의 크기는 2이상 100이하입니다. 따라서 rooms가 빈리스트인 경우는 없다는 것을 확인할 수 있습니다.
- rooms[i]의 길이는 0이상 1000입니다. 방안에 열쇠가 없을 수도 있다는 것을 의미합니다.
- 그런데 sum(rooms[i].length) 은 1이상 3000이하라고 합니다.
- 방안에 열쇠의 값은 0이상 n미만, 문제에서 주어진 0번방부터 n-1번방까지라는 것을 확인할 수 있습니다.
Output:
- 모든 방을 방문할 수 있으면 True, 그렇지 않으면 False를 반환합니다.

이제 문제 분석을 해보겠습니다.

Step2. 문제 분석하기

이전에 BFS, DFS가 쓰일것 같다고 했습니다. 왜냐하면 이 문제가 원하는 것은 모든 방을 방문할 수 있는지 없는지를 판단하는 문제이기 때문입니다. 즉, 각 방문을 정점이라고 한다면 모든 방을 방문한다는 것은 그래프 순회 알고리즘을 통해 모든 정점을 순회한다고 볼 수 있기 때문입니다. 실제 예시를 통해 확인해보겠습니다.

아래는 2번 예시를 그래프로 표현해보았습니다.

보시면, 2번 정점(방)은 갈 수가 없는 것을 확인할 수 있습니다. 이렇게 방을 그래프로 표현하면 그래프 순회 알고리즘인 DFS, BFS를 바로 사용할 수 있다는것을 확인할 수 있습니다.

그럼 이 내용을 기반으로 바로 코드 설계를 진행해보겠습니다.

Step3. 코드 설계

일단 시작 정점(방)은 0번 입니다. 0번 정점을 시작으로 순회를 시작하면 됩니다. 순회가 완료되었을 때 방문 기록에 모든 노드가 들어있으면 True, 그렇지 않으면 False를 반환합니다.

방문하는 과정은 DFS, BFS알고리즘을 모두 그대로 활용하면 됩니다.

바로 코드를 구현해보겠습니다.

Step4. 코드 구현

DFS

class Solution(object):
    def canVisitAllRooms(self, rooms):
        """
        :type rooms: List[List[int]]
        :rtype: bool
        """
        visited = [False] * len(rooms)
       
        def dfs(v):
            visited[v] = True
            for next_v in rooms[v]:
                if not visited[next_v]:
                    dfs(next_v)
            
        dfs(0)
        
        return all(visited)

코드 구현:

초기화
- visited 리스트를 만들어 모든 방의 방문 여부를 False로 초기화합니다.
- dfs 함수는 재귀적으로 방문 가능한 방을 탐색합니다.
DFS 동작
- 현재 방 v를 방문했다고 표시합니다: visited[v] = True.
- 현재 방 v에서 얻은 열쇠 목록을 순회하며, 아직 방문하지 않은 방을 dfs를 통해 탐색합니다.
결과 반환
- 모든 방을 방문했는지 all(visited)를 통해 확인하고 결과를 반환합니다.

시간 복잡도:

각 방(노드)을 한 번씩 방문하며, 방문한 방의 열쇠를 통해 연결된 방(간선)을 탐색합니다.
모든 방과 열쇠(간선)를 탐색하므로 시간 복잡도는 $O(V + E)$ 입니다.
- $V$ : 방의 개수 (노드 수)
- $E$ : 열쇠를 통해 열 수 있는 방문 가능한 방(간선 수)

결과:

https://leetcode.com/problems/keys-and-rooms/submissions/1455975278

BFS

from collections import deque
class Solution(object):
def canVisitAllRooms(self, rooms):
        """
        :type rooms: List[List[int]]
        :rtype: bool
        """
        
        visited = [False] * len(rooms)
        
        def bfs(v):
            queue = deque()
            queue.append(v)
            visited[v] = True
            while queue:
                cur_v = queue.popleft()
                for next_v in rooms[cur_v]:
                    if not visited[next_v]:
                        queue.append(next_v)
                        visited[next_v] = True
                
        bfs(0)
        
        return all(visited)

코드 설명:

초기화
- visited 리스트를 만들어 모든 방의 방문 여부를 False로 초기화합니다.
- queue를 초기화하고 시작 방 0을 추가합니다. visited[0] = True.
BFS 동작
- 큐에서 방을 하나씩 꺼내 현재 방에서 얻은 열쇠 목록을 확인합니다.
- 열쇠를 통해 방문 가능한 방 중에서 아직 방문하지 않은 방만 큐에 추가하고 방문 처리합니다.
결과 반환
- 모든 방을 방문했는지 all(visited)를 통해 확인하고 결과를 반환합니다.