DFS/BFS 문제

⚽ DFS/BFS 문제

격자에서 상하좌우로 연결되어 있는 집합(노드)들을 찾는 스타일의 문제들.

• 즉 한 지점에서 시작하여 퍼져나가는 스타일(블러드 필) → 연결 요소가 몇개인가?

⚽ 이런 문제들은 BFS/DFS 둘 중 아무거나 써서 풀 수 있어.

하지만 격자에서 여러 경로를 찾는 문제는 (출발점 → 도착점 끝까지 찍어봐야 하는 것) DFS를 써야하고, 격자에서 최단거리 탐색을 할 때는 BFS를 써야 한다.

😎 DFS가 유리한 경우

• 재귀적인 특징과 백트랙킹을 이용하여 모든 경우를 전부 탐색하는 경우
• graph의 크기가 클 경우
• Optimal한 답을 찾는 것이 아닌 경우
• 경로의 특징을 저장해야 하는 경우 ex) 경로의 가중치, 이동 과정에서의 제약

-> 즉 모든 경우의 수를 구해야 하는 경우 !! 검색 대상의 규모가 큰 경우!!

😎 BFS가 유리한 경우

• 최단거리 or 최단횟수 구하는 경우
• Optimal한 답을 찾는 경우, BFS는 가장 처음 발견되는 해답이 최단거리 !!
• 탐색의 횟수를 구해야 하는 경우

-> BFS는 항상 최단 경로를 보장한다. 최단 거리를 구해야 하는 경우!!