[알고리즘] DFS & BFS

코딩 테스트에서 자주 사용되는 알고리즘이자  탐색 알고리즘에서 가장 유명한 방법들인 DFS와 BFS를 알아볼 것이다.

 

📕DFS란?

DFS는 (Depth First Search)의 약칭으로 우리말로는 깊이 우선 탐색이라고 한다.

간단하게 말하면 트리나 그래프에서 한 루트로 최대한 깊숙하게 들어가면서 탐색한 뒤  다시 돌아가 다른 루트를 탐색하는 방법이다.

위의 그림처럼 1번에서 2번으로 간뒤 2번의 하위 트리를 끝까지 탐색한 후 되돌아가 다른 경로를 탐색한다.

대표적으로는 백트래킹[Backtracking]에 사용한다.

 

👍장점

• 현 견로상의 노드들만을 기억하면 되므로 저장 공간의 수요가 비교적 적다.
• 목표 노드가 깊은 단계에 있을수록, 그 노드가 좌측에 있을수록 BFS보다 해를 빨리 구할 수 있다.

👎단점

• 해가 없는 경로에 깊이 빠질 가능성이 있다.
• 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 DFS는 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해가 최적이 아닐 수 있다는 뜻이다.

💡구현

재귀호출과 스택으로 할 수 있다.

위의 그림으로 스택의 과정을 설명하겠다.

제일 먼저 트리의 root인 1을 스택에 넣는다.

stack에서 top부분에 있는 노드에서 인접 노드를 찾고 stack에서 push 함. (2번 노드임)

 

그 다음 스택에서 top에 위치한 원소에서 인접 노드를 찾고 stack에 push 함.(3번 노드임)

top 노드에서 인접노드가 없기 때문에 pop 하고 다시 top에 있는 방문 안 한 인접 노드를 찾고 push 함.(4번 노드)

이렇게 top에서 인접노드가 없다면 pop 하고 다시 top에서 방문 안 한 인접 노드를 찾음.(2번 노드)

위의 과정을 끝까지 한다면 위의 결과가 나오게 된다.

📕BFS란?

BFS는 (Breadth First Search)의 약칭으로 우리말로는 너비 우선 탐색이라고 한다.

트리나 그래프에서 출발점을 정하고, 출발점에서 갈 수 있는 모든 경로를 방문한 뒤 다시 연결되어 있는 모든 경로를 탐색한다.

그림으로 이해한다면 쉬울 것이다.

👍장점

1. 노드의 수가 적고 깊이가 얕은 경우 빠르게 동작할 수 있다.
2. 단순 검색 속도가 깊이 우선 탐색(DFS) 보다 빠르다.
3. 너비를 우선 탐색하기에 답이 되는 경로가 어려 개인 경우에도 최단경로임을 보장한다.
4. 최단경로가 존재한다면 어느 한 경로가 무한하게 깊어진다 해도 최단 경로를 반드시 찾을 수 있다.

👎단점

1. 재귀 호출의 DFS와는 달리 큐에 다음에 탐색할 정점들을 저장해야 하므로, 저장공간이 많이 필요하다.
2. 노드의 수가 늘어나면 탐색해야 하는 노드 또한 많아져서 현실적으로는 어렵다.

💡구현

queue를 사용해서 구현할 수 있다.

위의 그림으로 queue를 사용한 구현을 설명하겠다.

1. 시작 정점을 방문하고 큐에 넣는다.
2. 큐에서 가장 앞의 노드(front)를 빼고 해당 노드의 인접 노드(방문하지 않은 노드여야 함)를 방문하고 큐에 넣는다.
3. 큐가 빌 때까지 2번 과정을 반복함.

1. 큐에 시작 정점인 1을 넣는다.
2. 큐의 가장 앞의 노드인 1을 빼고 해당 노드의 인접 노드를 방문.
   • 2,3을 방문하고 큐에 넣는다.
3. 큐의 가장 앞의 노드인 2를 빼고 해당 노드의 인접노드를 방문.
   • 4,5를 방문하고 큐에 넣는다.

 

4. 큐의 가장 앞의 노드인 3을 빼고 해당 노드의 인접 노드를 방문.

• 6,7을 방문하고 큐에 넣는다.

5. 큐의 가장 앞의 노드인 4,5,6,7을 차례대로 빼고 인접 노드를 검사하지만 없으므로 실행을 종료함.