그래프를 탐색(= 노드를 하나씩 방문)할 때, DFS 와 BFS 방식을 사용할 수 있다.

DFS (깊이 우선 탐색)

하나의 분기를 끝까지 탐색하고, 해당 분기 탐색이 끝나면 그 다음 분기를 탐색하는 방법

예시 - 미로찾기

예를 들어, 미로찾기를 할 때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 그 갈림길부터 다시 다른 방향으로 탐색을 진행하는 것이 깊이 우선 탐색 방식이라고 할 수 있습니다.

특징

1. 🌟 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함
2. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함
3. 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림

구현 방식

스택 혹은 재귀함수로 구현할 수 있다.

BFS (너비 우선 탐색)

인접한 노드들을 먼저 탐색하는 방법

DFS는 최대한 깊게 이동한다면, BFS는 최대한 넓게 이동하는 방식이다.

예시

지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Sam과 Eddie사이에 존재하는 경로를 찾는 경우 → 두 노드 사이의 관계 파악..? 모르겠어용

특징