DFS와 BFS

참고블로그

DFS와 BFS

트리 순회(탐색)는 모든 자료(노드, 정점)를 빠짐없이 탐색하는 것을 의미한다. (완전 탐색)
그래프, 2차원 배열도 위의 기법으로 탐색할 수 있다.

DFS (Depth First Search)

1. 깊이 우선 탐색
2. 루트 노드(시작 정점, 출발 위치)에서 출발하여 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 노드(정점)로 되돌아와서 다른 방향의 노드(정점)으로 탐색을 계속 반복하여 결국 모든 노드(정점)을 방문하는 순회 방법
3. 가장 마지막에 만났던 갈림길의 노드(정점)로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출(Last-In First-Out) 자료구조인 스택(Stack)을 사용할 수 있다.
4. 재귀 함수는 시스템 스택을 이용하므로 이를 이용하여 간단하게 구현할 수도 있다.

// 순열처럼 기저조건까지 와야 답이 나오는 경우
// 경로의 개수 세기

BFS (Breadth First Search)

1. 너비 우선 탐색
2. 너비 우선 탐색은 탐색 루트 노드(시작 정점, 출발 위치)의 자식 노드(인접한 정점)들을 먼저 모두 차례로 방문한 후에 방문했던 자식 노드들(인접한 정점)을 시작점으로 하여 다시 해당 노드의 자식 노드(인접한 정점)들을 차례로 방문하는 방식
3. 자식 노드(인접한 정점)들에 대해 탐색을 한 후, 차례로 다시 너비 우선 탐색을 진행해야 하므로, 선입선출(First-In First-Out) 형태의 자료구조인 큐를 활용함
4. 너비 우선 탐색은 인접한 노드들부터 차례대로 방문을 하므로 시작 정점과 끝 정점이 주어졌을 때 최단 길이를 구할 수 있다.

// 중간에 답이 나오는 경우
// 끝가지 가는 것이 중요하지 않은 상황
// 최단거리 찾기
// 깊이가 너무 깊어서 함수콜(재귀)이 너무 많은 경우