1. 깊이 우선 탐색(DFS, Depth First Search)
최대한 깊이 내려간 뒤, 더 이상 갈 수 없을 경우 옆으로 이동
루트 노드(또는 다른 임의의 노드)에서 시작해 다음 분기로 넘어가기 전 해당 분기를 완벽하게 탐색하는 방식
- 모든 노드를 방문하고자 할 때 선택하는 방법
- DFS가 BFS보다 상대적으로 간단하지만, 탐색 속도는 느림
- 스택 또는 재귀함수로 구현
2. 너비 우선 탐색(BFS, Breadth First Search)
최대한 옆으로 넓게 이동한 뒤, 더 이상 갈 수 없을 경우 아래로 이동
루트 노트(또는 다른 임의의 노드)에서 시작해 인접한 노드를 먼저 탐색하는 방식
- 두 노드 사이의 최단 경로를 찾을 때 선택하는 방법
- 큐로 구현
스택(stack)과 큐(Queue)
스택(stack)
스택이란 쌓아 올리는 것을 의미한다.
말 그대로 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있다.
따라서 가장 위에 쌓인 자료가 곧 가장 최근에 들어온 자료를 의미한다.
이렇듯 스택은 시간 순서에 따라 자료가 쌓이기 때문에 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO, Last In First Out) 구조를 갖는다.
- 스택에서 자료를 삽입하는 연산은
push, 삭제하는 연산은pop
큐(Queue)
큐는 대기줄을 의미한다.
줄을 서서 버스를 기다릴 때 먼저 서 있던 사람이 먼저 타는 것처럼 선입선출(FIFO, First In First Out) 구조를 가진다.
스택은 정해진 한 곳(top)을 통해 삽입과 삭제가 이루어지는 반면,
큐는 한쪽 끝에선 삽입 작업, 반대편 끝에선 삭제 작업이 양쪽으로 이루어진다.
이때 삽입 연산만 진행되는 곳은 리어(rear), 삭제 연산만 진행되는 곳은 프론트(front)라고 하며,
큐의 리어에서 이루어지는 삽입 연산은 인큐(enQueue), 프론트에서 이루어지는 삭제 연산은 디큐(deQueue)라고 한다.
- 큐의 가장 첫 원소는 프론트 원소가 되며, 가장 나중에 들어온 원소는 리어 원소가 되는 것
참고
https://devuna.tistory.com/32
https://devuna.tistory.com/22
