DFS, BFS 기초

0. 들어가기 전에

1. 그래프 : 정점(node)과 간선(edge)으로 이루어진 자료 구조
2. 그래프 탐색 : 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것
3. DFS, BFS 모두 그래프 탐색의 일종
4. DFS, BFS는 target을 찾거나, 방문 경로를 출력하기에 활용

1. DFS (Depth First Search, 깊이 우선 탐색)

1. 최대한 깊이 내려간 뒤, 더 깊이 갈 곳이 없을 때 옆으로 이동
   = 하나의 node에서 시작하여 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색
2. 특징
   = 모든 노드를 방문하고자 할 때 사용
   = BFS에 비해 간단하나, 검색 속도는 느림

2. BFS (Breadth First Search, 너비 우선 탐색)

1. 최대한 넓게 이동한 뒤, 더 이상 갈 곳이 없을 때 아래로 이동
   = 하나의 node에서 인접한 node를 먼저 탐색
2. 특징
   = 두 node 사이의 최단 경로를 찾을 때 사용

3. 구현

# graph의 형태는 dict
# key값 = 특정 node
# value값 = 해당 node에 접한 node들의 리스트
# 알아둘 것 : list.extend는 list 끝에 가장 바깥 iterable의 모든 요소를 추가한다

graph = {
    'A': ['B'],
    'B': ['A', 'C', 'H'],
    'C': ['B', 'D'],
    'D': ['C', 'E', 'G'],
    'E': ['D', 'F'],
    'F': ['E'],
    'G': ['D'],
    'H': ['B', 'I', 'J', 'M'],
    'I': ['H'],
    'J': ['H', 'K'],
    'K': ['J', 'L'],
    'L': ['K'],
    'M': ['H']
}

1. DFS

# 방법 1. 
def dfs(graph, root):
    visited = []  #방문한 node를 차례대로 저장할 목록
    stack = []  #방문할 node를 차례대로 저장할 목록
    stack.append(root)
    
    while stack:  #방문할 곳이 없을 때까지 loop
        node = stack.pop()  #queue에서 node 꺼내오기
        if node not in visited:  #해당 node에 아직 방문하지 않았다면
            visited.append(node)  #해당 node를 방문 목록에 추가하고
            queue.extend(graph[node])  #queue에 해당 node의 자식 node를 추가해준다
            
    return visited
    
# 방법 2. 
def dfs(root):
    stack = [root]
    
    while True:
        if len(stack) == 0:
            print('All node searched.')
            return None
        
        node = stack.pop()
        if node == Target:
            print('Target found.')
            return node
        
        stack.extend(children)
        
# 방법 3. 재귀(recursive)
def dfs(graph, start, visited=[]):
    
    visited.append(start)
    
    for node in graph[start]:
        if node not in visited:
            dfs(graph, node, visited)
            
    return visited

2. BFS

# 방법 1. 
def bfs(graph, root):
    visited = []  #방문한 node를 차례대로 저장할 목록
    queue = []  #방문할 node를 차례대로 저장할 목록
    queue.append(root)
    
    while queue:  #방문할 곳이 없을 때까지 loop
        node = queue.pop(0)  #queue에서 맨앞 node 꺼내오기
        if node not in visited:  #해당 node에 아직 방문하지 않았다면
            visited.append(node)  #해당 node를 방문 목록에 추가하고
            queue.extend(graph[node])  #queue에 해당 node의 자식 node를 추가해준다
            
    return visited
    
# 방법 2. 
def bfs(root):
    queue = [root]
    
    while True:
        if len(queue) == 0:
            print('All node searched.')
            return None
        
        node = queue.pop(0)
        
        if node == Target:
            print('Target found.')
            return node
        
        queue.extend(children)
        
# 방법 3. deque
# deque는 popleft가 가능 → 시간복잡도가 O(1)
# 그냥 list에서 pop(0)하면 시간복잡도가 O(n)이기 때문에 deque가 유리
from collections import deque

def bfs(graph, root):
    visited = []
    queue = deque()
    queue.append(root)
    
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.append(node)
            queue.extend(graph[node])
            
    return visited  

4. 시간 복잡도

5. 문제 응용

1. 모든 노드 방문 : DFS, BFS
2. 경로의 특징(조건)을 저장해야 함 : DFS
3. 최단거리 찾기 : BFS