tree

[Algorithm] Breadth-First Search(BFS)

오늘의 알고리즘 Topic은 Breadth-first search(너비우선탐색)입니다.사실 BFS라고 더 많이 불리고 있습니다. BFS하면 짝꿍 DFS도 빠질 수 없습니다.DFS는 이후 게시글에서 알아보도록하고 오늘은 BFS를 먼저 살펴보겠습니다.특징BFS의 기본 개념은 Tree 구조에서 파생되었고, Tree의 노드를 순회하는 방식 중에 하나입니다.어떠한 자료구조를 순회할 때는 항상 기준이 중요합니다. BFS의 기준은 바로 현재 노드의 Depth입니다. Tree는 기본적으로 Depth라는 개념이 있습니다.Root 노드로부터 몇번째 자식노드냐에 따라 Depth가 정해집니다.위 사진에서 최상단의 붉은 원이 Root노드이며, 11 노드는 Root 노드로부터 3번째 노드이므로 Depth가 3입니다.Tree 노드..