[Algorithm] DFS/BFS

1. DFS

깊이우선탐색(depth-first search, DFS)은 맹목적 탐색 방법 중 하나로 탐색 트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용해 트리에 다음 Level의 한개의 자식 노드를 첨가하여, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다. 쉽게 설명하면 하나의 루트를 선택하여 최대한 깊이 들어가 확인한 후 다시 돌아가서 다른 루트를 탐색하는 방법이다. 구현 방법은 재귀 호출을 사용하면 된다. 

 

탐색 과정이 시작 노드에서 한없이 깊이 진행되는 것을 막기 위해 depth bound을 사용한다. depth bound에 도달할 때까지 목표 노드가 발견되지 않으면 최근에 첨가된 노드의 부모 노드로 돌아와 부모 노드에 이전과는 다른 동작자를 적용해 새로운 자식 노드를 생성한다. 여기서 부모 노드로 돌아오는 과정을 backtracking이라고 한다. 

 

만약 트리가 아닌 그래프를 탐색할 때는 약간의 변화가 필요하다. 우선 그래프에서 깊이를 결정해야 한다. 일반적으로 그래프에서는 루트 노드의 깊이를 0으로 하고, 임의의 노드 깊이는 이의 부모 중 가장 깊이가 작은 것의 깊이에 1을 더한 값으로 정의한다. 따라서 그래프에서 깊이우선탐색은 OPEN에 있는 노드 중 가장 깊은 것을 택해 확장시키게 된다. 자식 노드가 생성되어 이 중 이미 OPEN이나 CLOSED에 있는 것이 존재할 시, 재조정해야 한다. 

DFS

 - 장점

 단지 현 경로상 노드만 기억하면되므로 저장공간의 수요가 적음

 목표 노드가 깊은 곳에 존재할 경우 해를 빨리 구할 수 있음

 

 - 단점 

 해가 없는 경로에 깊이 빠질 가능성 존재. 따라서 실제 경우 미리 지정한 임의 깊이까지만 탐색후 목표노드를 발견하지 못하면 다음 경로를 따라 탐색하는 방법이 유용

 얻어진 해가 최단 경로라는 보장이 없음. 목표에 이르는 경로가 다수인 문제에 대해 DFS는 해에 다다르면 탐색을 끝내므로, 최적이 아닐 수 있음

DFS 예시

2. BFS

너비우선탐색(breadth-first search, BFS) 또한 맹목적 탐색 방법 중 하나로 루트 노드를 방문한 후 루트 노드에 인접한 모든 노드들을 우선으로 방문하는 방법이다. 더 이상 방문하지 않는 노드가 없을 때까지 방문하지 않은 모든 노드들에 대해서도 너비우선검색을 적용한다 OPEN List는 큐를 사용해야만 레벨 순서대로 접근이 가능하다. 

 

DFS와 가장 큰 차이로, 여러 갈래 중 무한한 길이를 가지는 경로가 존재하고 목표가 다른 경로에 존재하는 경우 DFS로 탐색시에는 무한한 길이의 경로에서 영원히 종료하지 못하지만,  BFS의 경우는 모든 경로를 동시에 진행하므로 탐색이 가능하다는 특징이 존재한다. 

 

 - 장점

 출발 노드에서 목표 노드까지 최단 길이 경로 보장

 

 - 단점 

 경로가 매우 길 경우 탐색 가지가 급격히 증가함에 따라 보다 많은 메모리 공간 필요

 해가 존재하지 않을 시 유한 그래프의 경우 모든 그래프를 탐색한 후 실패로 끝남

 무한 그래프의 경우 해를 찾지도 못하고 끝내지도 못함

BFS 예시

---

참고 문서

https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

깊이 우선 탐색 - 위키백과, 우리 모두의 백과사전