[코딩테스트] DFS, BFS 중 탐색 알고리즘 고르는 팁

아래 팁이 절대적인 기준은 아니다. 많은 문제를 풀어보면서 스스로 익히는 것이 최고이지만 시간이 부족하다면 팁이 필요할 것이다.

1. 탐색의 깊이(depth)가 깊다면 BFS일 가능성이 높다.

2. 위와 같은 이유로 2차원 맵이 크다면 BFS일 가능성이 높다.

3. 마찬가지로 탐색 가지(자식)수가 많아도 BFS일 가능성이 있다.

4. 반대로 깊이가 그리 깊지 않다면 DFS일 가능성이 있다 (대략 30이하 정도이려나요).

5. 이동이 제한적인 경우 DFS일 가능성이 있다. 예를 들어 sparse 한 2D array인 경우. 혹은 탐색 가지수(자식수)가 적은 경우.

6. 가지치기할 여지가 많다면 DFS일 가능성이 있다.

7. 2차원 배열에서 단순히 최소거리를 재는 것이라면 BFS로 하면 된다 (최소를 저장할 필요도 없다.).

8. 중복해서 visit해야하는 문제인 경우 DFS일 가능성이 있다.

본인은 PS 고수가 아니기 때문에 잘못된 내용일 수 있지만... 3개월 동안 전력을 다해 깨달은 결과입니다. 문제에서 탐색의 depth와 width를 고려하여 DFS와 BFS를 신중히 선택해야 합니다. 예를 들어, 경험상 2D array에서 단순 최소거리를 구하는 경우 BFS를 사용해야 합니다.

추가팁: DFS 문제 풀 시에 상태 원상복구를 항상 신경써야 합니다. 변하는 상태는 파라미터로 넘겨주는 것이 상책일 때가 있습니다.