깊이우선탐색(DFS), 너비우선탐색(BFS) 알고리즘

깊이 우선 탐색 (DFS)

: 깊이 우선 탐색은 깊은 부분을 우선적으로 탐색하는 알고리즘입니다.

• 그래프를 비롯한 비선형 자료구조에서 모든 자료를 빠짐없이 검색하는 방법 중에 하나 입니다.
• DFS는 스택 자료 구조 (혹은 재귀 함수)를 이용한다.

지도에 표시된 모든 곳에 들르기로 했는데, 길을 가다가 갈림길을 만났다고 가정해보자.

갈림길은 어느쪽이든, 들러야 하는 지점으로 향한다.

이렇게 갈림길에서 한쪽 방향을 고집하며 가장 깊게 들어가는 방식으로 탐색하는 방식을 깊이우선탐색이라고 부릅니다.

구현방법

1. 방문한 점에서 도달할 수 있는 점들을 살펴보고, 아직 방문하지 않은 점들의 정보를 스택에 PUSH한다.
2. 스택에서 점의 정보를 pop 하여 방문한다. 이후 다시 1번으로 돌아간다
3. 스택이 빌 때까지 반복한다.

• 정점들의 갯수와 간선 정보가 주어졌을 때,

1. 1번 정점에서 출발한다.
2. 작은 숫자를 가진 정점부터 방문한다

탐색 순서 : 1➡️2➡️4➡️6➡️5➡️3➡️7

문제를 풀어봅시다

---

너비 우선 탐색 (BFS)

너비우선탐색은 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘입니다.

• 큐 자료구조를 이용한다.

구현 방법

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에는 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
3. 더 이상 2번의 과정을 수행 할 수 없을 때까지 반복한다.

탐색 순서 : 1 ➡️ 2 ➡️ 3 ➡️ 8 ➡️ 7 ➡️ 4 ➡️ 5 ➡️ 6

(시작 노드부터 가까운 노드를 우선적으로 탐색한다 )