[알고리즘] Leetcode-keys-and-rooms 파이썬 문제 풀이

문제 링크

문제

2중 배열이 입력으로 주어지고 각 인덱스에 해당하는 방에 다른 방의 열쇠가 있다. 그 열쇠를 사용해서 주어진 모든 방에 들어갈 수 있으면 true, 하나라도 못들어가는 방이 있다면 false를 반환해주는 문제.

입출력 예시

조건

rooms.length, rooms[i].length의 곱이 시간복잡도에 직접적인 영향을 주는 요소이다. 최대 10의 6승이지만 잘 보면 sum(rooms[i].length가 3000이하이기 때문에 조금의 여유는 있다. O(n^2)보다는 낮은 시간복잡도를 가진 풀이법을 사용하자.

풀이 - BFS

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        visited = {}
        q = deque()
        q.append(0)
        visited[0] = True
        while q:
            cur_v = q.popleft()
            for next_v in rooms[cur_v]:
                if next_v not in visited:
                    visited[next_v] = True
                    q.append(next_v)
        
        return len(visited) == len(rooms)

전형적인 BFS 풀이 방법. visited를 Dictionary로 초기화 해주고, key를 얻은 순서대로 queue에 넣어서 탐색해주면 된다.
다 탐색한 후에 만약 visited의 길이와 rooms의 길이를 비교해서 같지 않다면 모든 방을 방문한 것이 아니기 때문에 False를, 같다면 모든 방을 방문한 것이기 때문에 True를 return한다.

풀이 - 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)
        return len(rooms) == len(visited)

풀이 개념은 BFS와 동일하다. 대신 재귀를 활용해서 DFS로 구현해주면 된다.