[코테 적용] [3번 문제] 완전탐색 (DFS, BFS)

출처 : 인프런 - 코딩테스트 [ ALL IN ONE ]

• Graph 활용

1. Graph 구현
2. DFS 깊이 우선 탐색
3. BFS 너비 우선 탐색

문제

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

접근방법

그래프로 추상화 할 수 있다.

다른 예시
DFS - O(V+E)

구현

• DFS

def canVisitAllRooms(roos):
    # visited = [] # 개선점 1)
    visited = [False] * len(rooms)
    
    
    # v 에 연결되어있는 모든 vertex에 방문
    def dfs(v):
        visited[v] = True # 방문
        for next_v in rooms[v]: # [1, 3]
            # if next_v not in visited: # 개선점 1) list에 쓰는 in은 개선
            #     dfs(next_v)
            if visited[next_v] == False:
                dfs(next_v)
    
    dfs(0)
    if len(visited) == len(rooms): 
        return True
    else: 
        return False
    


rooms = [[1, 3], [2, 4], [0], [4], [], [3, 4]]
print(canVisitAllRooms(rooms))

• BFS

from collections import deque

def canVisitAllRooms(roos):
    visited = [False] * len(rooms)

    # v 에 연결되어있는 모든 vertex에 방문
    def bfs(v):
        queue = deque()
        queue.append(v) # 방문 예약
        visited[v] = True # 방문
        while queue:
            cur_v = queue.popleft() # deque
            for next_v in rooms[cur_v]:
                if visited[next_v] == False:
                    queue.append(next_v)
                    visited[next_v] = True
    
    bfs(0)
    
    return all(visited)
    


rooms = [[1, 3], [2, 4], [0], [4], [], [3, 4]]
print(canVisitAllRooms(rooms))