트리 형태의 구조에 대해 이 트리를 탐색할 때 사용하는 탐색법에는 깊이 우선 탐색과 너비 우선 탐색 두 방법이 있다.
하나의 트리가 있을 때, 깊이 우선 탐색의 경우에는 기준 노드로 부터 하나의 자식 노드로만 내려간다. 점점 자식 노드로 내려가며 밑으로 파고드는 형태로 탐색을 수행하게 된다. 반면, 너비 우선 탐색은 하나의 노드가 가지고 있는 모든 자식들을 우선적으로 넓게 탐색하고, 이 자식들에 대해서도 노드 하나가 갖는 바로 아래 자식 노드를 넓게 탐색하며 내려가는 형태로 탐색하는 방법을 말한다.
이 글에서는 간단하게 구현 요령이나 어느 문제에서 활용하는 것이 유용할지에 대해 짤막하게 언급하고자 하기 때문에 자세한 설명은 우선 생략하겠다.
깊이 우선 탐색을 구현할 때는 보통 스택 자료구조를 사용해서 탐색을 수행한다.
자식 노드로 내려가며 탐색을 수행하는데, 더 이상 내려갈 자식 노드가 없다면 다시 위로 돌아와야 하는데, 이 돌아오는 과정에서 스택의 pop 연산을 통해 되돌아가는 식으로 구현이 되어야하기 때문이다.
그러나 스택을 일일이 구현해서 하는 방법 외에 재귀 함수 형태로 탐색을 구현하는 방법도 사용될 수 있다고 한다.
이 경우, 별도로 스택같은 자료 구조 구현이 필요 없다는 장점을 가지고 있다.
너비 우선 탐색은 큐를 이용해서 탐색 알고리즘이 구현된다.
큐 같은 경우에는 알고리즘 문제에서 사용 되는 일반적인 언어 (C++, Java, Python)에 표준 라이브러리로써 존재한다.
따라서 스택처럼 별도의 라이브러리를 불러온다거나 직접 구현한다던가 하는 번거로움이 없다는 이점이 있다.
그렇다면 이 두 탐색을 실전 알고리즘 문제에서 활용한다고 할 때, 어떠한 경우에 어떤 탐색법을 활용하는 것이 좋을까?
깊이 우선 탐색의 경우,
- 트리의 모든 경로를 탐색하고, 이에 대한 결과들을 일일이 확인해야만 한다
- 사전에서 특정 단어를 탐색하는 경우처럼 앞에서부터 탐색해서 찾는 것이 효율적인 경우에 대해
이 두 가지의 경우, 깊이 우선 탐색을 활용하는 것이 더 효율적이라고 한다.
반대로 너비 우선 탐색의 경우,
- 특정 지점에서 가장 가까운 것을 찾고자 하는 경우
- 탐색 범위가 굉장히 넓은 경우. 깊이 우선 탐색을 사용할 때 스택이 대량으로 발생한다면 너비 우선 탐색이 더 효율적이다.
- 특정 지점을 기준으로 어느 정도 근처에 구하고 싶은 해가 존재한다는 사실을 알고 있을 때
이러한 세 가지의 경우, 너비 우선 탐색을 사용해 문제를 해결하는 것이 보다 효율적이라고 한다.
