💡 유튜브 및 인프런을 보고 정리한 내용입니다!
문제시 해당 글은 삭제하도록 하겠습니다.
DFS vs BFS
만약 우리가 넷플릭스의 드라마를 볼 때 어떤 유형의 스타일인가?
하나를 몰아본다 ⇒ DFS(깊이 우선 탐색)
여러 개를 하나씩 본다 ⇒ BFS(너비 우선 탐색)
그래프: 여러 개채들이 연결되어 있는 자료 구조 / 정점(node)과 노드(edge)로 이루어진 자료 구조
탐색: 특정 개체를 찾기 위한 알고리즘
그래프 + 탐색 = 그래프(를) 탐색(하는) 알고리즘
그래프로 정보를 정리하는 이유는 탐색을 하기 위해서 이다.
(문제를 풀 때, 입력 값을 이차원 배열 등의 방법으로 정리한다.)
그래서 우리는 dfs 또는 bfs 를 검색하면 아래와 같이 그래프가 그려진 이미지들을 볼 수 있다.
DFS: 최대한 밑으로 가본 뒤, 없으면 옆으로 간다.
BFS: 최대한 옆으로 가본 뒤, 없으면 밑으로 간다.
대표적 문제 유형
1. 경로탐색 유형(최단 거리, 시간)
2. 네트워크 유형(연결)
3. 조합 유형(모든 조합 만들기)
구현 방법
DFS
- 재귀함수가 가장 일반적
- 모든 경우의 수를 확인
BFS
- Queue, LinkedList 를 사용
- 여러 놈을 확인하면서 가기 때문에 순서가 보장 되는 것이 중요하다.
결론
어떤 알고리즘을 사용해도 결과는 나오기 때문에 익숙한 알고리즘을 사용하자!
DFS는 정답이 나오는 시점에서 조합이 잘 나왔는지 확인하기가 빠르고 쉽다.
BFS는 조합이 완성되고 정답을 비교하는 시점에서 언제 어떻게 만들어졌는지, 어디서 틀렸는지 알기 어렵다!
DFS를 사용하는게 좋기는 하다.
하지만, DFS가 한 놈만 패는 알고리즘이기 때문에 한 놈이 너무 오래걸리면 시간 초과가 될 수 있다.
BFS는 오래 걸리는 것 같지만, 초반에 정답이 나오면 빠르게 처리 가능하다.
다시 말하면 대박날 확률도 적지만, 쪽박 찰 확률도 적다.(시간 복잡도가 낮다)
앞쪽에 쉬운 문제로 그래프 탐색 알고리즘이 나오면 DFS로 풀고
뒤쪽에 DFS로 풀기에는 시간이 오래 걸릴 것 같다면 BFS로 풀자
참고사이트
'프로그래밍 > 자료구조 && 알고리즘' 카테고리의 다른 글
[알고리즘] 피보나치 수열의 시간복잡도 (2) | 2024.07.24 |
---|---|
[알고리즘] 빅오(Big-O) 표기법 (0) | 2024.07.21 |
[Java] 큐(Queue) (0) | 2023.07.20 |
[Python] 해시 테이블(Hast Table) (0) | 2022.09.30 |
[Java] 배열(Array) (0) | 2022.09.27 |