03/18 알고리즘 문제풀이 - 841. Keys and Rooms (Leetcode)

문제

• Leetcode 알고리즘 문제
• 841. Keys and Rooms (Medium)
• 문제 내용 : [링크]
  
  

내가 작성한 코드

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        def dfs(curr_v):
            visited[curr_v] = True
            for next_v in graph[curr_v]:
                if visited[next_v] == False:
                    dfs(next_v)
                    
        visited = [False for _ in range(len(rooms))]
        graph = {}
        for i in range(len(rooms)):
            graph[i] = rooms[i]
            
        dfs(0)
        return all(visited)
        

• rooms에 있는 0번째 방부터, 모든 방을 확인할 수 있는지 물어보는 문제이다.

• dfs를 통해 rooms에 있는 방키들로 모든 방을 확인할 수 있는 지 검증한다.

• 먼저, 노드 방문여부를 확인할 visited 와 graph를 작성한다.

• 이후, dfs를 통해 방문가능한 모든 방(노드)를 탐색한다.

• visited가 모두 True이면(즉, 모든 방을 탐방하면) True, 아니면 False를 출력한다.

⭐

• BFS/DFS를 통해 방문 가능한 모든 노드를 탐색할 수 있다.

• 문제 상황을 graph 인접리스트로 만들 줄 알아야한다.