인프런 커뮤니티 질문&답변

안녕하세요 선생님, 강의를 듣던 중 궁금한 점이 생겨 질문을 드립니다.

https://www.acmicpc.net/source/share/ac40156090a44a3883d00e1da2250094

답지의 코드에서 ret == INF일 경우 -1을 출력하고 있는데, 유일하게 ret 갱신이 이루어지는 부분은 ret = min(cnt, ret);이기 때문에 ret값이 INF가 되려면 cnt가 INF이거나 그 이상이 되어야 할 것으로 보입니다.

백트래킹을 위해 추가된 코드 if (cnt >= ret) return; 이 있기 때문에 x, y 끝지점에 도달하기 전에 cnt >= ret일 경우 끝지점에서만 일어나는 ret 갱신이 일어나지 않기 때문에 ret는 INF일 수 있겠구나 생각했지만 그럴 경우 cnt >= ret이 되기 위해 cnt >= INF인 경우가 생기게 됩니다.

cnt >= ret이 아닌 이상 언젠가는 y == len에 도달하여 ret 갱신이 이루어질 것이고, 최초 dfs 호출 시 cnt를 0으로 주었기 때문에 cnt >= INF가 되기 위해선 실제로 cnt가 한 칸씩 증가할 수밖에 없습니다.

재귀를 통해 cnt를 하나씩 증가시킬 경우 INF에 도달하기까지 매우 많은 시간이 걸릴 텐데 어떻게 시간 초과가 나지 않는 것인지 궁금합니다.

시간 복잡도를 계산해봤을 때
재귀함수의 시간 복잡도는 O(갈래^깊이), 최악의 경우 for문 5번에서 재귀함수가 모두 호출 되므로 갈래 = 5, cnt를 1씩 증가시켜 INF에 도달하려면 깊이는 INF이므로 O(5^INF)라고 생각했는데 시간복잡도를 잘못 계산한 것일지 어떻게 INF일 때 시간 초과가 나지 않는 것인지 질문을 드립니다.