DFS/BFS

이전 영상의 내용이 개인적으로 너무 좋아서 해당 채널을 둘러보다가 보인 키워드!
해당 내용을 들어본 이유는 DFS/BFS가 코딩테스트에서 많이 출제되는 문제라는
이야기는 여러 커뮤니티에서 많이 들었다.
(웹개발 공부를 시작한지 얼마되지 않았을 때 들어볼 정도로..)
항해에서 이후에 배울 내용이지만 영상이 있어 한번 들어보았다.

여기서도 개인적으로 많은 것을 얻었다고 생각했다.

DFS/BFS

DFS = 하나를 몰아본다. => 깊이 우선 탐색
BFS = 여러 개를 한번에 본다. => 너비 우선 탐색

Point

• DFS/BFS는 그래프 탐색 알고리즘이다.
• 그래프는 여러 개체들이 연결되어 있는 자료구조를 말하며,
  이 개체들 중에서 특정 개체 A를 찾을 때 사용하는 알고리즘이기 때문에
  그래프 탐색 알고리즘 이라고 한다.

DFS/BFS의 대표적인 문제 유형
1. 경로탐색(최단거리, 시간)
2. 네트워크 유형 (연결)
3. 조합 유형(모든 조합 만들기)

=> 프로그래머스의 (타켓 넘버, 네트워크 단어변환, 여행경로) <=문제 등을 보고
DFS/BFS를 떠올렸다면 시간단축과 방향성을 잘 잡은 것.

DFS/BFS 구현방법

• DFS는 한놈만 팬다. ->(재귀함수 사용)
  재귀를 타고 타고 타서 탈출 조건에 먼저 도달하고 그 다음에 파라미터를 바꿔가면서
  정답을 찾는 방식으로 구현하게 된다.

• BFS는 여러 놈의 한대씩 때리면서 간다. ->(Queue/LikedList) 를 사용

1. 가장 먼저 넣었던 것을 꺼내서
2. 연결된 점을 Queue에 넣기
3. Queue가 빌때까지 반복

3. DFS? BFS 중 어떤 것을 써야할까!?

• 영상에서 설명한 개발자는 DFS를 선호한다고 했다.
  그 이유는 둘다 탐색을 하는 알고리즘이고 어떤 것을 써도 정답은 나오기 때문.
  자신있고, 손에 익은 알고리즘을 사용하면 됨
• DFS는 동작 검증이 쉬워 일일이 비교하기 때문에 선호한다
• BFS는 여러 조합을 한 칸 한 칸씩 만들다보니 조합이 완성되어서 정답과 비교하는 시점에
  정확히 언제 이렇게 생성되었는지 파악하기가 어렵다

근본적으로 우리는 코딩테스트를 준비하는 사람이다.
코테는 곧 시간싸움이며 짧은 시간 내에 알고리즘을 검증해야한다.
이를 위해 DFS가 적합하며, 재귀함수를 익히면 코드가 보다 간결하고
버그 가능성도 근본적으로 더 작다고 한다

BFS가 필요한 경우

• DFS가 한 놈만 패는 경우인데 시간이 오래걸리면 시간이 초과될 수 있다.
  DFS는 수행 시간 관점에 볼 때는 복불복이다. 운이 좋으면 첫번째 조합에서 최적의 답.
  최악의 경우에는 모든 조합을 다 만들어 보면서 시간을 낭비할 가능성이 있다.
  반면에 BFS는 모든 경우의 수를 한 걸음씩 나가기 때문에 초반에는 느릴 수 있으나
  하나의 정답을 찾고자 할 때도 시간 복잡도가 낮다.

실전 풀이요령

• 대부분의 TC(Test Case)들은 프로그래머스에서는 효율성 TC라고 해서
  너무 단순하게 생각하면 시간 초과로 실패한다.
  그러니 문제 순서와 난이도를 고려해서
  앞쪽의 쉬운 문제라면 = DFS
  뒤쪽의 어려운 문제라면 = DFS로 시간이 오래걸릴 것 같다면 처음부터 BFS 권장.

정리:

• DFS/BFS의 대표유형은 경로탐색,네트워크, 조합만들기
  DFS 는 재귀함수로 간단하게
  BFS 는 Queue / Likedlist로 활용하여 구현