깊이우선탐색 vs 넓이우선탐색
그래프를 탐색하는 데는 크게 이 두 가지 방법이 있다. 그래프의 탐색방식은 사실 트리탐색과 이론상으로는 거의 흡사하기 때문에, 트리를 탐색하는 코드를 먼저 보는 게 좋을 거 같다.
트리 - 깊이우선탐색
깊이우선탐색은 재귀를 이용하는 편이 코드가 깔끔해지고 편리하다. 다만 재귀를 사용하면 꼬리재귀가 아니면 O(n)의 공간복잡도가 추가됨을 잊으면 안 된다. ES6 가 도입되면서 js 에도 꼬리재귀를 사용할 수 있게 코드최적화가 되었으니 몇 년 지나면 현업에서도 이런 방식으로 트리를 탐색할 수 있을지도 모르겠다.
재귀를 사용할 수 없는 상황이라면, 스택을 사용하면 원칙적으로는 같은 로직을 구현할 수 있다. 모든 재귀는 이터레이티브한 방식으로 전환할 수 있다.
깊이우선탐색 방식으로 트리를 검색하는 방법은 총 세 가지가 있다. preOrder, inOrder, postOrder 로, pre / in / post는 현재 위치해 있는 노드를 언제 탐색하냐로 갈린다. pre는 탐색을 하고 하위 자식들을 찾으며, in은 좌측 > 자기자신 > 우측 순으로 탐색하며, post는 자식들을 다 탐색한 후에 본인을 탐색한다.
Code
// preOrder
public void preOrder(Node node) {
if(node == null) {
return;
}
System.out.println(node.data);
preOrder(node.right);
preOrder(node.left);
}
// inOrder
public void inOrder(Node node) {
if(node == null) {
return;
}
preOrder(node.right);
System.out.println(node.data);
preOrder(node.left);
}
// postOrder
public void postOrder(Node node) {
if(node == null) {
return;
}
preOrder(node.right);
preOrder(node.left);
System.out.println(node.data);
}
이와 같이 코드 자체는 거의 흡사하고, 단지 어느 타이밍에 자기 자신을 탐색하냐에 따라 post/pre/in이 갈리게 된다.
트리 - 넓이우선탐색
반면에 넓이우선탐색은 큐를 사용하게 된다. 넒이우선탐색을 통하여 트리를 탐색하면, level 단위로 트리를 탐색하게 된다. 1레벨의 노드를 다 탐색 > 2레벨 노드 탐색 > 3레벨 노드 탐색…이렇게 하여 리프 노드까지 다 탐색하게 되면 탐색이 종료된다.
Code
public void wideSearch(Node head) {
if(head == null) {
return;
}
List<Node> queue = new LinkedList<Node>();
queue.add(head);
while(!queue.isEmpty()) {
// Queue에서 node를 한개 꺼낸다.
Node target = queue.remove();
// 탐색한다.
System.out.println(target.data);
target.isSearched = true;
if(!target.left.isSearched) {
queue.add(target.left);
}
if(!target.right.isSearched) {
queue.add(target.right)
}
}
}큐를 사용하기 때문에 약간 복잡하지만 원리는 비슷하다. 자기 자신을 탐색한 후에, 자신의 자식들이 탐색되지 않은 상황이면 큐에 집어 넣는다. 큐는 선입선출이므로 level 단위로 탐색이 가능하다.
그래프의 경우로 확장
위의 두 가지 사례를 확인한 이유는, 그래프에서 깊이우선탐색과 넓이우선탐색이 어떤 상황에 활용되고, 트리와는 어떤 다른 점이 있는지 확인하기 위함이다.
그래프에서 깊이우선탐색을 하게 되면, 본질적으로는 위의 코드와 같게 된다. 레벨 단위로 탐색하는 게 아니기 때문에 깊이우선탐색으로 얻은 거리는 최단거리가 아니다. 정확히, 최단거리일 수도 있고 아닐 수도 있다.
깊이우선탐색 Code
public void searchDeep(Node head) {
if(head == null) {
return;
}
// 탐색했다고 표시
head.isSerached = true;
System.out.println(head.data);
for(int i = 0; i<head.near.length; i++) {
Node node = head.near[i];
if(!node.isSearched) {
searchDeep(node);
}
}
}- 대상 노드를 탐색한다
- node에 근접해 있는 모든 노드를 탐색하면서, 탐색되지 않은 노드가 있으면 재귀호출한다.
위의 코드랑 거의 흡사하다.
넓이우선탐색 Code
public void searchWide(Node head) {
if(head == null) {
return;
}
List<Node> queue = new LinkedList<Node>();
queue.add(head);
while(!queue.isEmpty()) {
Node node = queue.remove();
System.out.println(node.data);
node.isSearched = true;
for(int i = 0; i<node.near.length; i++) {
Node nearNode = node.near[i];
if(!nearNode.isSearched) {
queue.add(nearNode);
}
}
}
}이 부분 코드는 그래프 탐색과 거의 흡사하다.
결론
트리와 그래프의 정의는 다음과 같다.
- Tree : 사이클이 없는 그래프
- Graph : 일련의 꼭지점들과 그 사이를 잇는 변으로 이루어진 조합론적 구조
이렇게 되므로, tree는 그래프에 속한다고 볼 수 있다. 그러므로 트리의 깊이우선탐색 / 넓이우선탐색은 특수한 경우의 그래프 깊이우선탐색 / 넓이우선탐색이라고 볼 수 있을 거 같다. 하나를 이해하면 나머지 하나는 쉽게 이해할 수 있지 않을까 하는 생각이 든다.