[Algorithm] DFS: Depth First Search 깊이 우선 탐색

[Algorithm] DFS: Depth First Search 깊이 우선 탐색

DFS

알고리즘을 공부하다보면 반드시 한 번쯤은 들어보게 되고, 공부해야하는 알고리즘이 두가지가 있다. DFS 와 BFS이다. 오늘은 둘 중 DFS(Depth First Search) 알고리즘에 대해서 간단하게 먼저 알아보도록 하겠다.

이름에서 알 수 있듯, 먼저 깊게 쑥~ 들어가보고 옆으로 차근차근 옮겨가며 탐색을 하겠다는 뜻이다. 그림으로 표현하면 다음과 같다.

위 그림은 트리를 나타낸 그림이다. 각 층의 인덱스는 왼쪽부터 오른쪽으로 커진다고 가정하겠다.

먼저 1번 노드에서 탐색을 시작할 것이다. 1번 노드에서 출발하여 다음 자식노드인 2번과 3번 노드를 방문해야하는데, 이때 DFS는 2번 노드 방문 후 3번 노드가 아닌 4번노드, 즉 2번 노드의 자식 노드로 탐색을 이어나가는 것이다. 그 다음은 8번 노드를 방문하면서 트리에 존재하는 가장 끝 깊이까지 방문을 마치게 된다.

그렇다면 그 다음은 어떻게 될까? 1번까지 다시 거슬러 올라간 다음, 다음 끝점까지 다시 탐색을 하는걸까? 아니다. 8번 노드까지 탐색을 마친 뒤, 자신의 부모 노드가 가지는 다음 인덱스의 자식 노드로 이동한다. 이 경우에는 4번 노드가 자식 노드로 8번 노드밖에 가지지 않기 때문에, 4번 노드까지 탐색을 마친 상태가 된다. 그러므로 4번 노드의 부모 노드인 2번 노드로 이동한뒤, 다음 자식노드인 5번 노드의 끝 노드까지 탐색을 다시 시작한다.

위와 같은 순서가 되는 것이다. 그러면 9번 노드 다음은 10번 노드가 된다. 탐색이 진행되는 노드 번호를 정리하면 다음과 같다.

1 -> 2 -> 4 -> 8 -> 5 -> 9 -> 10 -> 3 -> 6 -> 11 -> 7 -> 12

Implementation

탐색 방법은 위와 같이 된다는 걸 알았으니, 이제 어떻게 구현하는지 알아볼 차례이다.

먼저 DFS는 스택 또는 재귀 호출 함수를 통해 구현하는 것이 일반적이다. 재귀 호출 함수 역시 스택의 범주이므로 어찌보면 당연한 얘기일수도있다. 현재는 재귀 호출 함수의 형태로 구현할 것이고, 코드는 다음과 같다.

def DFS(graph, index): print(index) if not graph[index].hasNextNode: return for childIndex in graph[index].children: DFS(graph, childIndex)

DFS를 구현할때(재귀 함수를 구현할때)는 탈출 조건을 반드시 작성해야한다. 그렇지 않으면 out of index 에러가 나거나, 함수가 계속 호출되며 out of memory 에러가 발생할 수 있다.

먼저 DFS 함수를 호출하면 그래프와 현재 노드의 인덱스를 parameter로 받는다. 최초로 함수를 실행한다면 DFS(graph, 1)의 형태가 될 것이다. 그 후에는 현재 노드의 인덱스를 출력하고, 현재 노드가 탈출 조건에 해당하는지 확인한다. 만약 현재 노드가 다음 방문할 노드가 없다면 연결된 그래프의 가장 깊은 부분까지 탐색을 완료했다는 의미이기 때문에, 바로 함수를 종료한다. 만약 현재 노드가 다음 자식 노드를 가진다면, 다음 자식노드들을 매개변수로 차례대로 다시 DFS 함수를 호출한다.

이처럼 구현을 해놓으면 위 그림과 같은 탐색방법으로 그래프를 탐색한다.

from http://wonyong2.tistory.com/19 by ccl(A) rewrite - 2021-10-18 23:26:58