[leetcode] Keys and Rooms - BFS/DFS

문제

Keys and Rooms 링크

분석

• 시간복잡도 (Time complexity): O( V + E )
  • V: # of vertex, E: # of edge
  • 이 문제는 O(1000 + 3000) 정도! -> BFS/DFS로 풀어도 충분!

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.

1번째 풀이 -> DFS

class Solution:
    def canVisitAllRooms(self, rooms) -> bool:
        n = len(rooms)
        visited = [False] * n
        def dfs(cur_v, depth):
            visited[cur_v] = True
            
            # base case
            if depth == n:
                return
            # distinct key가 없으면
            if len(rooms[cur_v]) == 0:
                return
            else:
                for g in rooms[cur_v]:
                    if (not visited[g]):
                        dfs(g, depth+1)
        
        dfs(0, 1)

        canVisit = True
        for i in range(n):
            if not visited[i]:
                canVisit = False
                break
        return canVisit
    

2번째 풀이 -> BFS

class Solution:
    def canVisitAllRooms(self, rooms) -> bool:
        # graph가 곧 rooms
        canVisit = True
        n = len(rooms)
        visited = [False] * n
        
        # start_v
        q = deque()
        q.append(0)
        visited[0] = True
        count = 1
        while q:
            if count == n:
                break
            cur_v = q.popleft()
            if len(rooms[cur_v]):
                for next_v in rooms[cur_v]:
                    if not visited[next_v]:
                        visited[next_v] = True
                        count+=1
                        q.append(next_v)
            else:
                continue

        # if any room is not visited
        for v in visited:
            if not v:
                canVisit = False
                
        return canVisit

시행착오

• 처음 코드 작성 시, rooms[cur_v]에 아무 원소도 없다면(distinct key를 가지고 있지 않을 때) 그냥 break를 하여 while문을 빠져나오도록 하였음.
• 하지만, q안에 원소가 아직 존재한다면 이전 들렀던 방에서 얻은 distinct key를 통해 다른 방을 방문할 수 있으므로 break가 아닌 continue를 작성해주어야한다.

1. 처음 코드 (잘못된 코드)

            if len(rooms[cur_v]):
                for next_v in rooms[cur_v]:
                    if not visited[next_v]:
                        visited[next_v] = True
                        count+=1
                        q.append(next_v)
            ###### 잘못된 코드 ######
            else:
                break # continue로 바꾸어주어야 한다.
           ########################
                

결과 확인 main function

if __name__ == "__main__":
    rooms = [[1,3],[1,4],[2,3,4,1],[],[4,3,2]]
    solution = Solution()
    canVisit = solution.canVisitAllRooms(rooms)
    print("canVisit?: ", canVisit)

결과!

canVisit?: True