알고리즘 - DFS(깊이) BFS(너비) 우선탐색

DFS / BFS 개념 설명

• 그래프 탐색 알고리즘

여기서 말하는 그래프는 여러 개체들이 연결되어 있는 자료구조를 의미하고
이 개체들 중에서 특정 개체를 찾기 위한 알고리즘을 탐색 이라고 한다

---

대표적인 문제 유형

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

EX. 프로그래머스 - 타겟 넘버, 네트워크, 단어 변환, 여행경로 등의 문제를 보고 위와 같은 문제 유형이구나를 인지할 줄 알아야 함

---

DFS / BFS 구현 방법

• DFS : 한 놈만 패는 구현 방식이기 때문에, 재귀함수가 가장 일반적인 구현 방법
  • 재귀를 타고, 타고, 타서 탈출 조건에 먼저 도달하고 그 다음 파라미터를 하나씩 바꿔가며 정답을 찾는 방식으로 구현
  • 동작 검증이 쉬운 편

예시
타겟 넘버

• BFS : 여러 놈을 한대씩 때리면서 가는 유형이기 때문에, Queue, LinkedList를 주로 사용하여 구현
  • 가장 먼저 넣었던 것을 꺼내서, 거기서 연결된 점을 Queue에 넣고 Queue가 빌 때까지 반복하며 정답을 찾는 방식으로 구현(꼭 순서가 보장되어야 함)
  • 동작 검증이 어려운 편

예시
여행경로