[그래프 탐색] BFS, DFS

DFS와 BFS 이번 포스팅에서는 DFS와 BFS에 대해서 자세히 설명하도록 하겠습니다. DFS(Depth First Search) : 깊이 우선 탐색 DFS는 맹목적 탐색 방법의 하나로 탐색 트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식 노드를 첨가하며, 첨가된 자식 노드가 목표 노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 나가는 방식입니다. 트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙히 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식입니다. 대표적으로 백트래킹(부모 노드로 되돌아오는 과정)에 사용합니다. 일반적으로 재귀 호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하..

원문링크 : [그래프 탐색] BFS, DFS