✅ DFS (깊이 우선 탐색) 쓰는 경우
경로 전체를 탐색해야 할 때
→ 예: "어디까지 갈 수 있는가?" "연결된 영역은 몇 개인가?"
백트래킹(모든 경우의 수 탐색)
→ 예: N-Queen, 미로 경로 찾기(최단거리 X, 모든 경로 탐색)
재귀로 구현이 간단할 때
→ 작은 문제를 반복적으로 풀기 좋음.
📌 예시 문제
2차원 배열에서 섬의 개수 세기
단지번호붙이기 (백준 2667)
퍼즐/조합 문제 (DFS로 경우의 수 다 찾아보기)
✅ BFS (너비 우선 탐색) 쓰는 경우
최단 거리 / 최소 횟수를 구해야 할 때
→ BFS는 한 단계씩 "동시에" 퍼져가기 때문에, 먼저 도착한 경로가 최단 경로.
가중치가 없는 그래프에서 거리 계산
→ 다익스트라(가중치 O)보다 단순한 경우 BFS로 충분.
레벨 단위 탐색이 필요한 경우
→ 예: "몇 단계 만에 도달할 수 있나?"
📌 예시 문제
미로 최단 거리 (백준 2178)
토마토 문제 (백준 7576) → 며칠 뒤 다 익는지 계산
네트워크 전염, 전파 문제 (컴퓨터 바이러스, 소문 퍼짐 등)
🚩 정리
DFS = 끝까지 들어가서 탐색 → 연결, 영역, 경우의 수
BFS = 가까운 것부터 차례차례 → 최단 거리, 최소 단계
🚩 정리
DFS: 깊게 파고드는 문제 (예: 연결 요소 찾기, 경로 탐색, 백트래킹)
BFS: 최단 거리 / 최소 시간 문제에 강함
