[알고리즘] DFS

DFS 개념

DFS : 깊이 우선 탐색 (==장자 우선 탐색)

<-> BFS : 너비 우선 탐색

완전 탐색 기법 중 하나

스택(재귀)를 사용함

재귀는 부를 때마다 함수를 시스템 스택에 쌓기 때문에 결국 스택을 사용한 것과 동일한 효과를 가져옴

시작지점에서부터 끝점까지 이동하면서 모든 경우의 수를 탐색

-> 저렴한 비용을 뽑는 문제에서 사용함

앞선 BFS 정리 자료에서 보셨겠지만, DFS는 BFS와 서로 상반되는 개념입니다.

DFS는 탐색 시 같은 level에 위치한 노드들을 먼저 탐색하는 BFS와 달리, 한쪽 방향으로 깊이 탐색한 후, 거슬러 올라가면서 나머지를 탐색하는 알고리즘입니다. 그래서 이를 첫번째 자식을 가장 먼저 생각하는 장자 우선 탐색이라고 생각하셔도 좋을 것 같습니다.

BFS : 2 -> 7 -> 5 -> 2 -> 6 -> 9 -> 5 -> 11 -> 4

DFS : 2 -> 7 -> 2 -> 6 -> 5 -> 11 -> 5 -> 9 -> 4

위 예제를 통해서 알 수 있듯이, 루트 노드의 다음 순회로 첫 번째 자식인 7을 탐색하며, 이후 7의 첫번째 자식인 2가 탐색 됩니다.

이후 자식이 없으면, 다시 부모 노드로 돌아가 다른 자식의 여부를 파악하고, 자식이 있다면 기존과 같은 작업을, 없다면 다시 부모 노드로 돌아가는 작업을 반복합니다.

이전 BFS는 너비 탐색을 위해서 Queue를 사용했습니다. 반면 DFS의 깊이 우선 탐색은 우리가 비선형 재귀를 통해서 모든 경우의 수를 찾아내는 것과 같은 형식을 볼 수 있습니다.

DFS는 앞선 문장에서 유추할 수 있듯이 재귀, 정확히는 스택을 이용하여 구할 수 있습니다.

DFS의 진행 순서는, 우선 루트 노드의 오른쪽 자식과 왼쪽 자식을 스택에 집어넣습니다.

(왼쪽에서 오른쪽으로 넣어도 상관은 없습니다. 다만 BFS와 같이 좌측을 우선으로 한 탐색을 보여드리기 위하여 우->좌 순서로 진행합니다.)

즉, 2의 자식인 5와 7이 순서대로 들어가게 됩니다.

스택은 위에 쌓인 순서대로 데이터가 빠져 나오기 때문에 다음은 7이 나올 것이고, 7의 자식인 6과 2가 순서대로 들어가게 됩니다.

다음 2는 자식이 없으므로 탐색이 끝나게 되고, 다음 스택에 저장된 6을 탐색합니다. 6은 자식이 있으므로 11과 5순서로 데이터가 들어가게 됩니다.

재귀는 함수로 구현되며, 함수는 호출 될 때마다 자체적으로 시스템 스택을 사용하여 관리되게 됩니다.

즉 우리는 재귀를 사용하면서 간접적으로 스택을 사용하게 되는 것이기 때문에 DFS를 스택으로 구현할 수 있습니다.

2차원 지도 탐색

- 대표적인 알고리즘 문제

저렴한 비용 뽑기

- 수영장