깊이 우선 탐색(DFS)
-
DFS는 말그대로 한쪽 방향을 정하고 깊이 파고들어 그쪽에 원하는 목표가 있는지 찾고 없을경우 다른 반대쪽을 찾는 방식
-
DFS는 스택을 이용한다.
-
모든 노드를 검사할 수 있다.
-
스택을 이용할 때 알아둬야할 점은 지나고 스택에 들어갔다온 노드는 다시 스택에 들어가지 않는다는 것이다.
스택을 활용하여 출력 및 스택을 설명해본다.
스택: A
출력: -
- root node가 스택에 들어간다.
- root node와 연결된 노드들을 스택에 넣기 위해 스택에 있는 노드 중 가장 위에 있는 노드(여기선 root node)를 꺼내 출력하고 연결된 노드를 넣는다.
스택: C B
출력: A
스택: C E D
출력: A B
스택: C E I H
출력: A B D
- I 와 H는 연결된 노드(스택에 한번 들어갔다온 노드는 제외)는 더이상 없으므로 I, H를 스택에서 꺼내 출력하고 끝이다.
스택: C E
출력: A B D H I
스택: C K J
출력: A B D H I E
- K 와 J는 연결된 노드(스택에 한번 들어갔다온 노드는 제외)는 더이상 없으므로 I, H를 스택에서 꺼내 출력하고 끝이다.
스택: C
출력: A B D H I E J K
스택: G F
출력: A B D H I E J K C
스택: G N L
출력: A B D H I E J K C F
스택: G
출력: A B D H I E J K C L N
스택: N
출력: A B D H I E J K C L N G
스택:
출력: A B D H I E J K C L N G N
- 스택을 사용하는 이유
- 스택을 이용하면 스택의 가장 위에 있는 노드가 꺼내지고 출력되면서 해당 노드와 연결된 자식 노드들을 스택에 넣어줌으로써 연결된 노드를 계속 검사할 수 있기 떄문이다.
너비 우선 탐색(BFS)
-
BFS는 말그대로 각 depth의 노드들을 다 탐색한 후에 다음 depth로 넘어가서 탐색하는 방식이다.
-
BFS는 큐를 사용한다.
-
큐를 사용할 때 알아둬야할 점은 스택에 들어갔다온 노드는 다시 큐에 들어가지 않는 것이다. 또한 큐에서 나올때 출력된다.
큐를 활용하여 출력 및 스택을 설명해본다.
-
root node가 큐에 들어간다.
-
root node에 연결된 node를 큐에 넣기 위해 큐의 가장 앞에 값을 꺼내고 해당 값에 연결된 노드들을 큐에 넣는다.
큐: A
출력: -
큐: B C
출력: A
큐: C D E
출력: A B
큐: D E F G
출력: A B C
큐: E F G H I
출력: A B C D
큐: F G H I J K
출력: A B C D E
큐: G H I J K L N
출력: A B C D E F
- 큐에 남은 노드들은 연결된 노드(큐에 한번 들어갔다온 노드 제외)는 없기 때문에 큐에서 꺼내 출력만 하면 된다.
큐: -
출력: A B C D E F G H I J K L N
- 큐를 사용하는 이유
- 큐를 이용하면 선입선출 방식으로 데이터가 입력, 출력되는데 예를 들어 큐에 가장 앞에 있는 노드가 디큐되고 출력되면서 해당 노드와 연결된 자식 노드들을 인큐한다면 큐에 가장 뒤에 쌓이게 되고 Sibling Node들이 큐에 앞에 위치하기 때문에 자연스레 같은 depth의 노드를 다 탐색하고 다음 depth로 넘어갈 수 있따.
