DFS & BFS

DFS와 BFS는 모두 그래프 완전 탐색 기법이다.

🔰DFS(Depth First Search)

시작 노드에서 출발하여 매번 한 쪽 분기를 선택하여 최대 깊이까지 탐색을 마치고 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.

재귀 함수로 구현하거나, 스택 자료구조를 이용한다. 재귀 함수를 이용할 시 스택 오버플로를 주의하자.

시간 복잡도는 O(V + E)다(V: 노드의 수, E: 엣지의 수). 

DFS 응용 문제에는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등이 있다.

DFS는 한 번 방문한 노드를 다시 방문하면 안 되므로, 방문 여부를 확인할 배열이 필요하다.

인접 리스트로 표현된 그래프가 있다고 했을 때, 스택과 방문 여부를 확인하는 배열을 이용해서 DFS를 구현할 수 있다.

1. 시작 노드를 스택에 push한다. 
2. 스택에서 pop한 노드와 연결된 노드들을 찾는다.
3. 만약 이미 방문한 노드면 넘어가고, 방문한 적 없는 노드는 스택에 push 후 방문 여부를 갱신한다.
4. 위 과정을 스택에 아무 노드도 남지 않을 때까지 반복한다.

🔰BFS(Breadth First Search)

시작 노드에서 출발하여 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.

목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장한다.

queue 자료구조를 이용한다.

시간 복잡도는 O(V + E)다(V: 노드의 수, E: 엣지의 수).

인접 리스트로 표현된 그래프가 있다고 했을 때, 큐와 방문 여부를 확인하는 배열을 이용해서 BFS를 구현할 수 있다.

1. 시작 노드를 큐에 enqueue한다.
2. 큐에서 dequeue한 노드와 연결된 노드들을 찾는다.
3. 만약 이미 방문한 노드면 넘어가고, 방문한 적 없는 노드는 큐에 enqueue 후 방문 여부를 갱신한다.
4. 위 과정을 큐에 아무 노드도 남지 않을 때까지 반복한다.