[ Algorithm ] DFS와 BFS 알고리즘

1. DFS, 깊이 우선 탐색 (Deep-First-Search)

깊이 우선 탐색은그래프나 트리 자료구조에서 모든 노드를 한번씩 탐색할때 쓰이는 기본적인 방법이다.

완전탐색을 할 때 가장 간단한 방법 중 한가지다.

스택(Stack) 자료구조를 사용하는 것이 일반적이다.

 

DFS 기본 동작 방식

1. 시작 노드를 스택에 넣은 후 방문처리 한다.
2. 스택에 마지막으로 들어온 노드에 방문하지 않은 인접노드의 존재 여부를 확인한다.
   방문하지 않은 노드가 존재한다면 노드를 스택에 넣고 방문처리한다.
   없다면 현재의 노드 즉, 스택에 마지막으로 들어온 노드를 스택에서 추출한다.
3. 2번 과정을 반복할 수 없을때까지 반복해준다.

 

DFS 구현 특징

• 스택 사용을 사용하거나 재귀함수를 사용한다.
• 재귀함수는 스택과 동작원리가 동일하기 때문에 구현의 편리성이 존재한다.
• 완전 탐색을 목적으로 하는 경우에는 BFS보다 느릴 수 있기 때문에 적재적소에 사용하는 것이 좋다.
• 탐색속도가 느리더라도 구현의 편리함 때문에 BFS대신 DFS를 사용하는 경우도 적지않다.

 

DFS를 사용하는 경우는?

1. 간결한 코드로 구현해야 할 떄
2. 큐 라이브러리를 사용할 수 없을 때
3. 트리에서 최단 거리를 탄색해야 할 때
   -> 트리에서는 두 노드를 잇는 경로가 하나만 존재하는 경우만

 

 

2. BFS, 너비 우선 탐색 (Breadth-First-Search)

깊이 우선 탐색과 마찬가지로 그래프나 트리에서 모든 노드를 한번씩 탐색할때 쓰이는 알고리즘이다

모든 간선의 길이가 동일하게 주어졌을때 최단거리를 탐색하기 위한 목적으로 사용할 수 있으며

큐(Queue) 자료구조를 사용한다.

 

BFS 기본 동작 방식

1. 시작 노드를 큐에넣고 방문처리를 해준다.
2. 큐에서 원소를 dequeue(삭제/꺼내기) 해주어 방문하지 않은 인접한 노드를 확인한다.
   방문하지 않은 인접노드가 있다면 해당 노드를 큐에 모두 삽입하며 방문처리한다.
3. 2번 과정을 반복할 수 없을때까지 반복해준다.

 

BFS를 사용하는 경우는?

1. 간선의 비용이 모두 동일하게 주어졌을때 최단거리 문제를 해결할 때
2. 완전 탐색을 DFS로 진행했을때 메모리 혹은 시간초과되는 경우