때로는 무식한 게 더 효과적일 때가 있다

이번 문제에서는 너비 우선 탐색(BFS)으로 풀지 않고 해결할 수 있는 코드를 살펴봤습니다. 현재 시점에서 BFS를 안다는 것은 코딩 테스트에 대해 어느 정도 경험이 있고 관련 지식이 있다는 의미입니다. 그렇다면 왜 BFS를 사용하지 않고 이렇게 풀었을까요?

BFS는 현재 자신의 위치에서 상하좌우 네 방향으로 뻗어나가면서 경우의 수를 확인하는, 즉 어떤 위치에서 존재하는 모든 방향으로 퍼져나가면서 조건을 만족하는지 확인하는 탐색 방식입니다. 즉, 이 과정에서 탐색할 필요가 없는 요소까지 전부 확인한다는 의미입니다.

반대로 6가지 경우의 수만 따져서 바로 판단하면 for 문 2개라는 고정된 최대 연산 횟수에 불가능한 조합의 검출만 하면 되므로 더욱 빠르게 실행됩니다.

문제에서 제공되는 예제 1을 기반으로 테스트했을 때 BFS는 총 63번의 탐색 과정을 거치지만, 경우의 수는 26번만 탐색합니다. 따라서 무조건 이것은 BFS로 해결해야 하는 문제다!라고 단정 짓지 말고, 전체 탐색이 의미가 있는지 충분히 고민한 후 적용해야 합니다.

▼ 표 3-1 BFS와 6가지 경우의 수 사용 비교