003. 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)

글쓴이 / 2024년 07월 27일

먼저, 깊이 우선 탐색(DFS)에 대해 살펴 봅니다

위 이미지를 사용하여 깊이 우선 탐색(DFS) 알고리즘에 대해 설명해 드리겠습니다.

이 이미지는 이진 트리 구조를 보여주고 있습니다. DFS 알고리즘이 이 트리를 어떻게 탐색할지 설명하겠습니다:

  1. 시작: 루트 노드인 1에서 시작합니다.
  2. 왼쪽 우선 탐색:
    • 1 -> 2 -> 3 -> 4로 이동합니다.
    • 4는 리프 노드이므로, 3으로 백트래킹합니다.
    • 3의 오른쪽 자식인 5를 방문합니다.
    • 5도 리프 노드이므로, 2로 백트래킹합니다.
    • 2의 오른쪽 자식인 6을 방문합니다.
  3. 중간 노드 탐색:
    • 6에서 더 이상 자식이 없으므로, 1로 백트래킹합니다.
    • 1의 중간 자식인 7을 방문합니다.
  4. 오른쪽 서브트리 탐색:
    • 7에서 자식이 없으므로, 다시 1로 백트래킹합니다.
    • 1의 오른쪽 자식인 8로 이동합니다.
    • 8 -> 9 -> 10으로 이동합니다.
    • 10은 리프 노드이므로, 9로 백트래킹합니다.
    • 9의 오른쪽 자식인 11을 방문합니다.
    • 11에서 8로 백트래킹하고, 8의 오른쪽 자식인 12를 마지막으로 방문합니다.

따라서 DFS의 방문 순서는 다음과 같습니다: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12

이 과정에서 DFS는 항상 가능한 한 깊이 들어가며, 더 이상 갈 곳이 없을 때만 백트래킹하여 다른 경로를 탐색합니다. 이 방식으로 트리의 모든 노드를 효율적으로 방문할 수 있습니다.

깊이 우선 탐색을 구현하는 파이썬 코드는 아래와 같습니다.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.middle = None  # 중간 자식을 위한 추가 포인터

def dfs(node):
    if node is None:
        return
    
    print(node.value, end=' ')  # 현재 노드 방문
    
    dfs(node.left)    # 왼쪽 서브트리 탐색
    dfs(node.middle)  # 중간 서브트리 탐색
    dfs(node.right)   # 오른쪽 서브트리 탐색

# 트리 구성
root = Node(1)
root.left = Node(2)
root.middle = Node(7)
root.right = Node(8)

root.left.left = Node(3)
root.left.right = Node(6)

root.left.left.left = Node(4)
root.left.left.right = Node(5)

root.right.left = Node(9)
root.right.right = Node(12)

root.right.left.left = Node(10)
root.right.left.right = Node(11)

# DFS 실행
print("DFS 순회 결과:")
dfs(root)

다음으로 너비 우선 탐색에 대해서 살펴 봅니다.

너비 우선 탐색은 트리나 그래프 구조에서 노드를 탐색하는 방법 중 하나로, 루트 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방식입니다. 아래 이미지의 트리를 기준으로 BFS 과정을 설명하겠습니다:

  1. 시작: 루트 노드인 1에서 시작합니다.
  2. 첫 번째 레벨:
    • 1의 모든 자식 노드인 2, 3, 4를 순서대로 방문합니다.
  3. 두 번째 레벨:
    • 2의 자식 노드인 5, 6을 방문합니다.
    • 3은 자식이 없으므로 넘어갑니다.
    • 4의 자식 노드인 7, 8을 방문합니다.
  4. 세 번째 레벨:
    • 5의 자식 노드인 9, 10을 방문합니다.
    • 6, 7은 자식이 없으므로 넘어갑니다.
    • 8의 자식 노드인 11, 12를 방문합니다.

따라서 BFS의 방문 순서는 다음과 같습니다: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12

BFS의 주요 특징:

  1. 같은 레벨에 있는 노드들을 모두 방문한 후 다음 레벨로 넘어갑니다.
  2. 주로 큐(Queue) 자료구조를 사용하여 구현합니다.
  3. 출발점에서 가까운 노드부터 탐색하므로, 최단 경로 문제 해결에 적합합니다.
  4. 메모리 사용량이 DFS에 비해 크지만, 목표 노드가 얕은 깊이에 있을 때 효율적입니다.

BFS는 네트워크 탐색, 최단 경로 찾기, 웹 크롤링 등 다양한 분야에서 활용됩니다.

너비 우선 탐색의 파이썬 코드는 아래와 같습니다.

from collections import deque

class Node:
    def __init__(self, value):
        self.value = value
        self.children = []

def bfs(root):
    if not root:
        return

    queue = deque([root])
    result = []

    while queue:
        node = queue.popleft()
        result.append(node.value)

        for child in node.children:
            queue.append(child)

    return result

# 트리 구성
root = Node(1)
root.children = [Node(2), Node(3), Node(4)]
root.children[0].children = [Node(5), Node(6)]
root.children[2].children = [Node(7), Node(8)]
root.children[0].children[0].children = [Node(9), Node(10)]
root.children[2].children[1].children = [Node(11), Node(12)]

# BFS 실행
bfs_result = bfs(root)
print("BFS 순회 결과:", bfs_result)

Post Views: 57
Scroll to Top