[Algorithm] DFS & BFS 이해하기

DFS : 한 드라마를 몰아서 본다(Stack이나 재귀함수를 사용)

BFS : 여러 드라마를 한 편씩 본다.(Queue나 LinkedList를 사용)

 

DFS  또는 BFS로 풀어야 하는 대표적인 유형

1. 경로 탐색 유형(최단거리, 시간)
2. 네트워크 유형(연결)
3. 조합 유형(모든 조합 만들기)

 

DFS가 동작 검증이 쉽다.

하나씩 조합을 만들어서 정답과 비교하기 때문에 조합이 잘 나왔는지 확인이 쉽다.

하지만 수행 시간 관점에서는 복불복

운이 좋으면 첫 번째 조합이 최적의 답, 최악의 경우에는 모든 조합을 다 만들어 보면서 시간을 낭비하게 된다.

 

BFS는 한 번에 여러 조합들을 한 칸 한 칸씩 만들다 보니 조합이 완성되어 정답과 비교하는 시점에
언제 이렇게 만들어졌는지 또는 어디서부터 틀린 건지 분석하기가 까다롭다.

초반에는 느려 보일 수 있지만 하나의 정답만 찾고 나면 나머지 경우의 수는 정답에서 제외된다.

가장 먼저 넣었던 것을 꺼내기 => 연결된 점을 Queue에 넣기 => Queue가 비워질 때까지 반복

 

코딩 테스트에서 앞에 출제된 문제는 DFS로, 뒤에 출제된 문제는 탐색 시간이 오래 걸릴 거 같다면 BFS로 푸는 것을 추천한다.