[알고리즘] DFS vs BFS: 문제 유형부터 선택 기준까지

https://www.youtube.com/watch?v=BsYbdUnKZ-Y

https://www.youtube.com/embed/BsYbdUnKZ-Y

| 드라마로 이해하는 DFS/BFS

1) 드라마 볼 때의 유형

• 끝나길 기다리고 몰아본다.

• 드라마 여러 개를 다 챙겨본다.

2) 이게 DFS/BFS의 전부!!

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

• 여러 개를 하나씩 보다 = BFS (너비 우선 탐색)

| DFS/BFS 문제 유형

1) 그래프 탐색 알고리즘

• 그래프 : 여러 개체들이 연결되어 있는 자료 구조

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

2) 대표적 문제 유형

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

• 네트워크 유형 (연결)

• 조합 유형 (모든 조합 만들기)

-> 프로그래머스의 타겟 넘버, 네트워크, 단어 변환, 여행 경로 등의 문제를 보고 DFS/BFS를 떠올렸다면, 최소한의 방향으 정확하게 잡고 가는거라, 초반에 시간을 낭비하는 일은 없다.

| DFS/BFS 구현 방법

1) DFS

• 한 놈만 끝까지 패는 유형이기에, 재귀함수가 가장 일반적

• 재귀를 타고타고 들어가서, 탈출 조건에 먼저 도달하고, 그 다음에 파라미터를 하나씩 바꿔 가면서 정답을 찾는 방식

2) BFS

• 여러 놈을 한대씩 때리면서 가는 유형이기에, Queue / LinkedList를 사용하는 것이 보편적이다.

• 턴을 돌면서, 가장 먼저 넣었던 것을 꺼내서, 연결된 점을 Queue에 넣고, Queue가 빌 때까지 반복한다.

• 순서가 보장되어야 하기에, Queue / LinkedList를 사용한다.

| DFS/BFS 중에 어떤 걸 써야할까

1) 본인은 DFS를 더 선호한다.

• 둘다 탐색을 하는 알고리즘이기에, 어떤걸 써도 정답은 나오기에, 자신 있고 손에 익은 알고리즘을 사용하는 것이 좋다.

• DFS를 선호하는 이유는 동작검증을 하기 쉽기 때문이다. DFS는 어찌 됐든 하나의 조합을 완성해서 정답과 비교하고, 또 다른 조합을 만들어 보고, 정답과 비교하는 식으로 동작하기 때문에, 정답을 비교하는 시점에 내가 기대한 대로, 조합이 잘 나왔는지를 확인하기가 빠르고 쉽다.

• 그에 비해 BFS는 한 번에 여러 조합들을 한칸 한칸씩 만들다보니, 조합이 완성되어서 정답과 비교하는 시점에 이것이 언제 어떻게 이렇게 만들어졌는지, 어디서부터 틀려먹은거지를 분석하기가 까다롭다.

2) 하지만, BFS가 필요할 때가 있다.

• DFS가 한 놈만 패는 알고리즘인데, 한 놈이 너무 오래 걸리면 시간이 초과될 수 있다. 다르게 설명하면, DFS는 수행 시간 관점에서 복불복일 수 있다는 점이다. 운이 좋으면 첫 번째 조합이 최적의 답이 될 수 있지만, 최악의 경우 모든 조합을 다 만들어보면서 시간을 크게 낭비하게 된다.

• 그에 비해 BFS는 모든 경우의 수를 한 걸음씩 나가기 떄문에, 초반에는 느려보일 수 있지만, 하나의 정답만 찾고자면, 나머지 경우의 수는 정답에서 제외된다. 쉽게 말하면, 대박날 확률도 적지만, 쪽박 찰 확률도 적다는것이다. 즉, 시간복잡도가 낮다.