WEEK03- TIL DFS와 BFS

DFS 기본 구현

1. 시작 노드에서 방문하지 않았으면 노드를 삽입해준다  == 방문 표시

2. 더 이상 방문이 불가능하다면, 탐색 중단하고 이전으로 돌아옴

 

*특징

1. 스택 or 재귀함수 사용

2. 한 방향으로 깊게 탐색

3. 깊이 제한 횟수를 늘려주자!

 

sys.setrecursionlimit(10**8) #깊이 제한 

def dfs(arr, cur, visited):
    visited[cur] = True
    for i in arr[cur]:
        if not visited[i]:
            dfs(arr, cur, visited)
            
            
# 나는 dfs(arr, cur, visited) 부분을 defaultdict를 이용해 graph에 담아서 사용

def dfs(v):
    visited[v]=1
    print(v,end=' ')
    for i in graph[v]:
        if not graph[i]:
            dfs(i)

 

BFS 기본 구현

1. 시작 노드에서 방문하지 않은 인접 노드를 큐에 삽입 == 방문 표시

2. 큐가 빌 때까지 큐에서 하나씩 꺼내서 방문하지 않은 인접 노드를 큐에 삽입 == 방문 표시

 

*특징

1. 큐를 사용 [덱이 더 효율적이라 deque로!]

2. 매 순간이 최적의 경우를 보장

3. 방문 체크를 큐에 넣기 전에 해줘야 한다

→ 불필요한 방문이 큐에 쌓여서 중복으로 방문되는 경우가 생겨, 메모리 초과가 발생

from collections import deque

def bfs(arr, start, visitet):
    queue = deque([start])
    visited[start] = True
    while queue:
        cur = queue.popleft()
        for i in arr[cur]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

 

 

참고