[LeetCode] 841. Keys and Rooms

문제 링크: https://leetcode.com/problems/keys-and-rooms/description/

Keys and Rooms - LeetCode

코드

• DFS

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        visited = set() 

   
        def dfs(v):
            visited.add(v)
            for next_v in rooms[v]:
                if next_v not in visited:
                    dfs(next_v)



        dfs(0)
        if len(visited) == len(rooms) : return True
        else: return False

• BFS

from collections import deque
class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        visited = set() #5번방 방문 안했네 => False  // True
        
        def bfs(v):
            visited.add(v)
            q = deque()
            q.append(v)
            while q:
                tmp = q.popleft()
                for i in rooms[tmp]:
                    if i not in visited:
                        visited.add(i)
                        q.append(i)
        bfs(0)
        if len(visited) == len(rooms) : return True
        else: return False

풀이

• DFS,BFS를 짤 줄 안다면 쉽게 풀 수 있다.
• visited를 set으로 초기화한 이유는, 조건문에서 찾고자 하는 값이 배열에 있는지 확인할 때의 시간 복잡도를 줄이기 위해서이다.
• 파이썬에서 딕셔너리와 셋은 해시로 이루어져 있기 때문에 in 으로 찾을때 시간 복잡도가 O(1) 이다.
• 리스트의 경우, 순서가 있기 때문에 in 으로 찾을 때의 시간복잡도는 O(n)으로 효율이 좋지 않다.
• dfs,bfs를 진행할 때 visited를 통해 방문했는지 안했는지를 조건문을 통해 확인하면 된다.