[DFS] leetcode 841번 Keys and Rooms, class이해

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

Keys and Rooms - LeetCode

 

# 문제

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.

 

# 코드

class Solution:
    def dfs(self, graph, v, visited, keys):
        
        visited[v] = True # 방문완료
        # key 초기화
        for i in graph[v]:
            keys[i] = True # 들어갈 수 있음.

        # key들을 차례대로 반복
        # if: 방문하지 않았는데 키가 있을때만 dfs
        for i in graph[v]: # true만
            if not visited[i] and keys[i]:
                self.dfs(graph, i, visited, keys)
    
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
          
        visited = [False]*len(rooms)
        keys = [False]*len(rooms) # key들의 뭉치
        print(visited)

        self.dfs(rooms, 0, visited, keys)
        
        # for i in len(vi)
        # print("visited: ", visited)
        # print("keys: ", keys)
        return all(visited)

기존 dfs에서 방문확인할 때, key가 있는 방만 들어갈 수 있는 조건을 추가하여 진행하면 된다.

=> and keys[i] 만 추가한다.

 

leetcode는 class를 이용해서 문제를 낸다.

"같은 class내의 메서드를 호출할 때"에는 self키워드를 사용하여 메서드를 호출해야 한다.

 => self.dfs(graph, i, visited, keys)의  사용이유

 

파이썬 class 내의 메서드는 첫 번째 매개변수로 "self"를 사용해야 한다.

 

https://codewizard.tistory.com/36

[Python] class와 self

참고해 주세요.