탐색(1): 깊이 우선 탐색/너비 우선 탐색

※ DFS, BFS는 인접행렬 또는 인접리스트를 이용하여 탐색한다.

깊이 우선 탐색 (DFS: depth-first search)

그래프 완전 탐색 기법 중 하나로, 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후, 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘

 

- 후입선출의 스택 자료구조를 이용

- 재귀함수를 이용하여 구현하므로, 스택 오버플로우 (stack overflow) 주의

- 한 번 방문한 노드를 재방문하지 않도록 방문 여부를 체크할 리스트가 필요

 

* 탐색 과정:

(i) 탐색을 시작할 노드를 선택하여 스택에 삽입하고 방문 여부를 체크한다.

(ii) 스택의 최상단에 있는 노드를 꺼내어, 인접 노드의 방문 여부를 확인한다.

    → 방문하지 않은 노드라면, 스택에 삽입 & 방문 체크

(iii) 스택 자료구조에 값이 없을 때까지 위 두번째 과정을 반복한다.

 

넓이 우선 탐색 (BFS: breadth-first search)

 

그래프 완전 탐색 기법 중 하나로, 시작 노드에서 출발하여 가까운 노드를 먼저 방문하면서 탐색을 수행하는 알고리즘

- 선입선출의 큐 자료구조를 이용

- 시작 노드로부터 가까운 노드를 우선으로 하여 탐색하므로, 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장

- 한 번 방문한 노드를 재방문하지 않도록 방문 여부를 체크할 리스트가 필요

 

* 탐색 과정:

(i) 큐를 생성하여, 탐색할 시작 노드를 큐에 삽입하고, 방문 여부를 체크한다. deque()

(ii) 큐에서 노드를 꺼내어, 인접 노드의 방문 여부를 확인한다. queue.popleft()

    → 방문하지 않은 노드라면, 큐에 삽입 & 방문 체크

(iii) 큐 자료구조에 값이 없을 때까지 위 두번째 과정을 반복한다.