DFS(깊이 우선 탐색), BFS(너비 우선 탐색)

알고리즘 공부를 하다보면 필수적으로 나오는 DFS, BFS에 대해서 정리하고자 한다. 우선적으로 그래프란 간선과 노드로 이루어진 구조로, 연결된 객체간의 관계를 정의할 수 있는 자료 구조이다.

아래의 예에서 노드는 A, B, C 와 같은 목적지이고, 간선은 노드와 노드 사이를 연결해주는 길 이라고 생각해보자. 특정 노드에서 출발하여서 다른 노드로 도착하는 경로를 이 포스팅에서 설명하는 DFS와 BFS로 예시를 들어서 설명할 예정이다.

DFS(Depth First Search) DFS는 말 그래도 깊이 우선 탐색으로, 시작 지점에서부터 깊은 곳까지의 탐색을 끝까지 진행한 뒤에, 다음 경로를 탐색하는 방식을 사용한다. DFS는 재귀적인 특징이 있어서 전체 노드를 모두 탐색하는 경우에 주로 사용된다.

위의 그래프를 예로 들면 (A, B, D, E, F, I) 로 첫 번째 A에서부터 연결된 가장 깊은 I까지의 탐색을 1차적으로 진행한다. 그 후로는 F, E, D, B, A로 상위 경로를 거...