BFS vs DFS 둘 다 가능한 경우, BFS를 써라

(잡담)요즘 매일 매일 알고리즘 문제를 풀어나가는 중이다. Github의 잔디밭을 채우는 재미와 함께 문제를 해결했을 때 쾌감이 쏠쏠하다.

‘이것이 코딩테스트다’라는 책을 차근차근 따라가며 문제를 풀던 중, 백준 온라인 저지(BOJ)에서 인구이동(16234번)이라는 문제를 접하게 되었다. 문제를 해결하는 아이디어 자체는 그다지 어려운 문제가 아니었다.

관건은 BFS, DFS 둘 다로 해결할 수 있을 듯한 문제였는데, 나는 DFS를 선택하여 먼저 구현을 하였다. 하지만 Python3에서는 시간 초과가 났고.. Pypy3에서는 메모리 초과가 발생하였다. 아무리 코드를 최적화시켜도 시간을 맞출 수가 없었다. 결국 검색을 해보았는데 나와 정말 같은 상황이었던 포스팅을 발견하여 이곳에 간략하게(서론보다 짧을 듯..) 정리해보려한다.

— BFS가 일반적으로 DFS보다 수행속도가 빠르다. 그러니 둘 다 가능해 보인다면 BFS를 사용하자.(참고. ‘이것이 코딩테스트다.’)

— 파이썬은 재귀함수를 호출할 수 있는 한계점이 있다.
sys.setrecursionlimit()를 사용하면 파이썬 인터프리터의 스택제한을 설정할 수 있다. 재귀함수 호출 depth가 아닌 인터프리터의 스택제한을 설정하는 것임에 유의하자.

From the python docs this function:
Set the maximum depth of the Python interpreter stack to limit. This limit prevents infinite recursion from causing an overflow of the C stack and crashing Python. The highest possible limit is platform-dependent. A user may need to set the limit higher when she has a program that requires deep recursion and a platform that supports a higher limit. This should be done with care because a too-high limit can lead to a crash.

— 시험 시간이 좀 남아있으면, 꼬일 때 잠깐 머리식히는 것도 방법인 듯 하다.

Ref:
1. https://docs.python.org/2/library/sys.html#sys.setrecursionlimit
2. https://dailyheumsi.tistory.com/61
3. https://stackoverflow.com/questions/7081448/python-max-recursion-question-about-sys-setrecursionlimit