너비 우선 탐색(Breadth-first search)와 깊이 우선 탐색(Depth-first search)

in Blog / 알고리즘

  • 트리에서는 폭 우선/가로 우선/수평 검색이라고 하며, 낮은 레벨부터 왼쪽에서 오른쪽으로 검색해

  • 트리 제외하고는 큐(Queue)를 사용해서 구현해

from collections import deque

def bfs(graph, start):
    visited = {node: False for node in graph} # visited 딕셔너리에 graph의 모든 노드 받아와서 node:False 저장
    queue = deque([start]) # start를 deque로 변환
    visited[start] = True # visited[start] == False 였는데, True로 변환

    while queue: # queue에 원소가 있을때
        v = queue.popleft() # queue의 앞 원소 출력, 그것이 v가 됨
        print(v, end=' ')  # 방문 노드 출력

        for neighbor in graph[v]: # graph[0] 안에는 [2,3] 존재
            if not visited[neighbor]: # visited[2] 가 이웃(같은 레벨)이고 False라면,
                queue.append(neighbor) # 큐에 2를 넣는다
                visited[neighbor] = True # visited[2]의 값을 True로 변경

# 그래프 예시 (인접 리스트 방식)
graph = {
    1: [2, 3],
    2: [4, 5],
    3: [],
    4: [],
    5: []
}

bfs(graph, 1)  # 1부터 탐색 시작, 1 2 3 4 5 출력

  • 트리에서는 세로/수직 검색이라고 하며, 리프에 도달할 때까지 아래쪽으로 내려가면서 검색, 리프에 도달하면 부모에 다시 돌아가 다시 또 내려간다.

  • 이진 트리에서 깊이 우선 검색은 세 종류의 스캔 방법이 있는데, 아래와 같아

  • 전위 순회 : 노드 방문 -> 왼쪽 자식 -> 오른쪽 자식

def preorder(node):
    if node is None:
        return
    print(node.value)
    preorder(node.left)
    preorder(node.right)
  • 중위 순회 : 왼쪽 자식 -> 노드 방문 -> 오른쪽 자식
def inorder(node):
    if node is None:
        return
    inorder(node.left)
    print(node.value)
    inorder(node.right)
  • 후위 순회 : 왼쪽 자식 -> 오른쪽 자식 -> 노드 방문
def postorder(node):
    if node is None:
        return
    postorder(node.left)
    postorder(node.right)
    print(node.value)

위 같은 경우 이진 트리에서 사용이 되고 그래프에서의 DFS에 대한 함수 아래에 가져와 봤어

그래프에서의 DFS는 재귀 또는 스택을 사용해

def dfs(graph, v, visited): 
    visited[v] = True # 방문한 위치 False → True로 값 변경
    print(v, end=' ')  # 방문 노드 출력

    for neighbor in graph[v]:
        if not visited[neighbor]:
            dfs(graph, neighbor, visited) # 재귀 함수

# 그래프 예시 (인접 리스트 방식)
graph = {
    1: [2, 3],
    2: [4, 5],
    3: [],
    4: [],
    5: []
}

visited = {node: False for node in graph}  # 방문 여부 초기화

dfs(graph, 1, visited)  # 1부터 탐색 시작,  1 2 4 5 3 출력

BFS/DFS 마무리

일반 그래프에서의 DFS와 이진 트리에서의 DFS가 어떻게 다른지 아래 표로 정리해 봤어

항목일반 DFS (그래프)전/중/후위 순회 (이진 트리)
대상그래프 (사이클 가능 : 돌아오는 것)이진 트리 (사이클 없음)
순서방문 순서만 중요하지 않음순서 매우 중요
구현재귀 / 스택재귀
용도경로 탐색, 연결 요소 탐색 등트리 구조 분석, 정렬 등

그리고 아래는 그래프에서의 DFS vs BFS에 대한 요약이야

항목DFSBFS
구조스택 (혹은 재귀)큐
구현 방식보통 재귀 함수 사용큐 자료구조 사용
사용 예시미로 탈출, 백트래킹 등최단 경로 탐색, 레벨 탐색 등

마지막으로 BFS/DFS 사용 가능한 자료 구조 표야

구조설명
트리(이진 트리 포함)노드 간에 부모-자식 관계가 있는 구조. 사이클 없음
그래프노드와 간선으로 이루어진 일반적인 구조, 사이클 존재 가능. 방향 그래프, 무방향 그래프 모두 포함
격자(Grid)2차원 배열 형태의 공간도 그래프로 간주 가능(미로 문제 등)
상태 공간 그래프퍼즐, 게임판, 혹은 알고리즘 문제에서 상태를 노드로 보고 탐색하는 경우

© 2022 JeongHwan Yun.