[탐색] DFS vs BFS - 간단 정리

💡 유튜브 및 인프런을 보고 정리한 내용입니다!

 

문제시 해당 글은 삭제하도록 하겠습니다.

 

참고 사이트

 

DFS vs BFS

 

만약 우리가 넷플릭스의 드라마를 볼 때 어떤 유형의 스타일인가?

 

하나를 몰아본다  ⇒ DFS(깊이 우선 탐색)

여러 개를 하나씩 본다 ⇒ BFS(너비 우선 탐색)

 

그래프: 여러 개채들이 연결되어 있는 자료 구조 / 정점(node)과 노드(edge)로 이루어진 자료 구조

탐색: 특정 개체를 찾기 위한 알고리즘

 

그래프  + 탐색 = 그래프(를) 탐색(하는) 알고리즘

 

 

그래프로 정보를 정리하는 이유는 탐색을 하기 위해서 이다.

(문제를 풀 때, 입력 값을 이차원 배열 등의 방법으로 정리한다.)

 

그래서 우리는 dfs 또는 bfs 를 검색하면 아래와 같이 그래프가 그려진 이미지들을 볼 수 있다.

 

구글 검색했을 때, 나오는 이미지들

 

DFS: 최대한 밑으로 가본 뒤, 없으면 옆으로 간다.

BFS: 최대한 옆으로 가본 뒤, 없으면 밑으로 간다.

 

왼쪽: DFS / 오른쪽 BFS

 

 

대표적 문제 유형

1. 경로탐색 유형(최단 거리, 시간)

2. 네트워크 유형(연결)

3. 조합 유형(모든 조합 만들기)

 

 

구현 방법

DFS

• 재귀함수가 가장 일반적
• 모든 경우의 수를 확인

 

BFS

• Queue, LinkedList 를 사용
• 여러 놈을 확인하면서 가기 때문에 순서가 보장 되는 것이 중요하다.

 

결론

어떤 알고리즘을 사용해도 결과는 나오기 때문에 익숙한 알고리즘을 사용하자!

 

DFS는 정답이 나오는 시점에서 조합이 잘 나왔는지 확인하기가 빠르고 쉽다.

BFS는 조합이 완성되고 정답을 비교하는 시점에서 언제 어떻게 만들어졌는지, 어디서 틀렸는지 알기 어렵다!

 

DFS를 사용하는게 좋기는 하다.

 

하지만, DFS가 한 놈만 패는 알고리즘이기 때문에 한 놈이 너무 오래걸리면 시간 초과가 될 수 있다.

 

BFS는 오래 걸리는 것 같지만, 초반에 정답이 나오면 빠르게 처리 가능하다.

다시 말하면 대박날 확률도 적지만, 쪽박 찰 확률도 적다.(시간 복잡도가 낮다)

 

앞쪽에 쉬운 문제로 그래프 탐색 알고리즘이 나오면 DFS로 풀고

뒤쪽에 DFS로 풀기에는 시간이 오래 걸릴 것 같다면 BFS로 풀자

 

참고사이트

• https://youtu.be/BsYbdUnKZ-Y