[질문] 초보적인 문제 시간복잡도 질문드립니다.

[?(211.187)]

https://www.acmicpc.net/problem/2178

이 문제 BFS로 풀어야 한다는 것은 알고 있습니다만

만약 DFS로 푼다고 가정할 때 시간복잡도가 정확하게 어떻게 되는지 잘 모르겠습니다.

도움 부탁드립니다.

[시아닌(kimjg1119)]

대충 3^(NM)

[?(211.187)]

잘 이해가 안가서 그러는데 조금 풀어서 설명해주실수 있나요??

[시아닌(kimjg1119)]

칸이 무한히 많아서 위 아래 왼쪽 오른쪽 중 방금 갔던 방향 빼고 항상 갈 수 있다고 생각해봐. 그러면 한번 갈때 선택할 수 있는 경우는 3가지. 갈 수 있는 칸의 개수는 nm개. 실제로는 이것보다 훨씬 빠르겠지

[?(211.187)]

아 이제 이해됬습니다 ㅎㅎ 정말 감사합니다 !!