오늘 알아볼 알고리즘은 BFS !!
너비 우선 탐색 (BFS, Breadth-First Search)이라는 알고리즘입니다.
아래와 같은 순서로 설명을 진행해보겠습니다 🔥
- BFS의 개념
- BFS의 특징
- BFS의 구현
BFS의 개념
BFS, 너비 우선 탐색이란 ?
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.
BFS에서의 노드 탐색 순서
너비 우선 탐색이기 때문에 깊이가 가장 얕은 노드부터 모두 탐색한뒤 깊이가 깊은 노드를 탐색하는 방법. 즉, 그림에서 깊이가 1인 노드1과 노드2를 먼저 탐색한뒤, 깊이가 1인 노드를 모두 탐색하였으므로 깊이가 2인 노드인 노드3, 노드4, 노드5, 노드6을 탐색하는 순서입니다.
BFS의 특징
-
직관적이지 않은 면이 있다.
=> BFS는 시작 노드에서 시작해서 거리에 따라 단계별로 탐색한다고 볼 수 있다. -
BFS는 재귀적으로 동작하지 않는다. (주의할 점 !!)
-
이 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다.
=> 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다. -
BFS는 방문한 노드들을 차례로 저장한 후(append) 처음부터 꺼낼 수 있는 (pop) 자료 구조인 큐(Queue)를 사용한다.
=> 즉, 선입선출(FIFO) 원칙으로 탐색
BFS의 구현
// pseudocode
BFS (G, start_v)
let Q be a queue
label start_v as discovered
Q.enqueue(start_v)
while Q is not empty do
v := Q.dequeue()
if v is the goal then
return v
for all edges from v to w in G.adjacentEdges(v) do
if w is not labeled as discovered then
label w as discovered
w.parent := v
Q.enqueue(w)수도 코드로는 뭔가 찝찝합니다. 똥 안닦은거 같은
leetcode 문제를 통해 bfs를 적용해보겠습니다.
Leetcode 104. Maximum Depth of Binary Tree
Given the root of a binary tree, return its maximum depth.
A binary tree's maximum depth is the number of nodes
along the longest path from the root node down to the farthest
leaf node.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if root is None:
# 루트가 비어있으면 바로 리턴
return 0
queue = collections.deque([root])
depth = 0
while queue:
depth += 1
# 큐 연산 추출 노드의 자식 노드 삽입
for _ in range(len(queue)):
cur_root = queue.popleft()
# cur_root 는 큐의 제일 왼쪽 꺼
if cur_root.left:
queue.append(cur_root.left)
if cur_root.right:
queue.append(cur_root.right)
# BFS 반복 횟수 => 깊이
return depth
난이도는 쉬운편 이지만, BFS 를 처음 접하는 분이 BFS를 이해하기엔 충분한 문제라고 생각합니다. 확실하게 이해하고 넘어갑시다 🤓
