[알고리즘] BFS/DFS

평소에는 DFS, BFS 둘 중 뭘 써도 풀리는 문제들만 풀었어서 차이점(효율적인 측면)을 명확하게 잘 몰랐다.

 

그렇게 오늘도 알고리즘 문제를 풀다 갑자기 이 DFS BFS 적용 기준 정리에 필요성을 느껴 바로 실행에 옮기려 한다.

 

BFS, DFS가 뭐야?

내가 알고있는  bfs, dfs는 그래프를 탐색하는 방법으로 알 고 있다.

각 dfs bfs에 대해 간단히 적어보겠다.

 

BFS(너비 우선 탐색)

• 큐를 사용함
• 정점에서 가까운 노드들부터 탐색
• 찾는 노드가 인접할 때 유리
• 노드가 많을 수록 메모리를 많이 소비

DFS(깊이 우선 탐색)

• 스택 혹은 재위함수를 사용함
• 정점에서 가장 깊은 노드까지 들어가며 탐색
• 그래프의 깊이(depth)가 깊을 수록 빠름
• 메모리가 적음

언제 뭐 써야해?

공통

• 단순히 모든 정점을 방문하는 것이 중요한 문제는 뭘 써도 상관이 없다
• 둘 중 더 손에 익은 걸루 하면 된다

BFS(너비 우선 탐색)

• 최단거리를 구하는 문제 ( 예) 미로 찾기 )는 bfs를 사용한다.
• bfs는 루트에서 가장 가까운 곳부터 탐색하기 때문에 처음 발견한 경로가 최단 경로가 된다.
• 반면 dfs는 처음 발견한 경로가 최단경로가 아닐 수 있다.
• 길 찾기, 라우팅
• 웹 크롤러
• 그래프에서 주변 위치 찾기

DFS(깊이 우선 탐색)

• 검색 대상의 그래프가 큰 경우에는 dfs를 고려해야한다.
• 경로의 특징을 저장해줘야 하는 문제 (예) a에서 b까지 가는 길에 c를 몇 번 이상 만나면 안된다.) 는 dfs를 사용한다.
• bfs는 경로의 특징을 가지지 못한다.

 

경로(과정)를 신경쓰면 dfs

최단(거리) 등 을 원하면 bfs

 

앞으로 그래프 탐색 문제를 접하면 위 내용을 상기하며 효율적인 탐색법을 사용하도록 노력해야겠다.