[정글 WEEK03_알고리즘] 개발 일지 - BFS/DFS

개요

BFS와 DFS는 그래프를 탐색하는 방법이고, 그래프 중에서도 트리에 많이 사용된다.

트리는 형제 노드의 순서 관계 여부에 따라 '순서 트리(Ordered Tree)', '무순서 트리(Unordered Tree)'로 구분할 수 있다.

참고로, 대표적인 순서 트리에는 이진 트리가 있다. 

순서 트리를 순회하는 방법에는 DFS 기반의 전위 순회, 중위 순회, 후위 순회가 있으며,

무순서 트리의 탐색에는 DFS 방식, BFS 방식 모두 사용할 수 있다. 

 

순서 트리 순회

아래와 같은 트리를 전위 순회, 중위 순회, 후위 순회 해보자.

         A
       /    \
     B     C
    /  \       \
  D    E      F

  - 전위 순회

   Root → Left → Right 순으로 탐색한다. 위 트리를 전위 순회한 결과는 A→B→D→E→C→F이다. 

   : 트리 직렬화/역직렬화, 트리 복원, 구조 출력 등 트리의 구조를 먼저 파악하는 것이 중요할 때 사용

     예시 문제)

      - 백준 1991. 트리 순회

      - 백준 2263. 트리의 순회

      - LeetCode 100. Same Tree

      - 트리 → 배열 변환 (Serialize)

      - 재귀적으로 "위에서 아래로" 처리 시

 

  - 중위 순회

   Left → Root → Right 순으로 탐색한다. 위 트리를 중위 순회한 결과는 D→B→E→A→C→F이다.

   : 항상 오름차순으로 출력하기 때문에 BST, 정렬 등 값의 순서가 중요할 때 사용

     예시 문제)

      - 백준 5639. 이진 검색 트리

      - 백준 14725. 개미굴

      - LeetCode 94. Binary Tree Inorder Traversal

      - BST Validation

      - 정렬된 데이터 만들기

 

  - 후위 순회

   Left →Right→ Root 순으로 탐색한다. 위 트리를 후위 순회한 결과는 D→E→B→F→C→A이다.

   : 서브 트리 정보 수집, DP, 트리 삭제, 수식 평가 등 자식 노드의 정보를 모두 확인 후 부모 노드를 처리할 때 사용

     예시 문제)

      - 백준 11725. 트리의 부모 찾기

      - 백준 15681. 트리와 쿼리

      - LeetCode 145. Binary Tree Postorder Traversal

      - LeetCode 337. House Robber III (DP on Tree)

      - 삭제 관련 문제 (메모리 해제)

 

https://jaemunbro.medium.com/python-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EB%8C%80%EB%B9%84-cheat-sheet-839a0681738f

 

DFS(Depth-First Search)

'깊이 우선 탐색' 알고리즘으로, 스택이나 재귀를 이용하여 최대한 멀리 있는 노드를 우선으로 탐색

 1. 탐색 시작 노드를 스택에 삽입하고 방문처리

 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리

      방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼냄

 3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복 

 

구현

# 재귀

def dfs_recursive(graph, v, visted):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs_recursive(graph, i, visited)

visited = [False] * (len(graph) + 1)
dfs_recursive(graph, 1, visited)

# 스택

def_stack(graph, start_node):
    stack = []
    visit = []
    
    stack.append(start_node)
    
    while stack:
        node = stack.pop()
        if node not in visit:
            visit.append(node)
            stack.extend(graph[node])
 
    return visit

 

BFS(Breadth-First Search)

'너비 우선 탐색' 알고리즘으로, 큐를 이용해 가까운 노드부터 탐색

1. 탐색 시작 노드를 큐에 삽입하고 방문처리

2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입 후 방문처리

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복

 

구현

from collections import deque

def bfs(graph, start):
    queue = deque([start])
    visisted = [False] * len(graph) + 1
    
    visited[start] = True
    while queue:
        v = queue.popleft()
        print(v, end = ' ')
        for i n graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
                
bfs(graph, 1)