일단 동서남북 4방향으로 재귀를 진행하다보면 같은 칸을 다시 계산하는 경우가 있으며,

이에 대한 처리가 없다면 무한 루프에 빠집니다.

캐시는 -1로 초기화하고

if(cache[y][x]!= -1) return cache[y][x];

int ans = 0;

for(4방향에 대해서)

   if(좌표 범위, 높이에 대한 체크 만족)

           ans += solve(next_y, next_x)

return cache[y][x] = ans;


이런 식으로 하면 무한루프가 납니다.

다른 분들 풀이를 본 결과,

if(cache[y][x]!= -1) return cache[y][x];
cache[y][x] = 0;
for(4방향에 대해서)
   if(좌표 범위, 높이에 대한 체크 만족) 

       cache[y][x] += solve(next_y, next_x) 

return cache[y][x];

이렇게

하위 작업에 대한 재귀호출이 마치자 마자 바로 해를 캐시에 반영하면 무한 루프에 빠지지 않습니다.


어떤 원리로 이렇게 되는지 궁금합니다.


cache[y][x] = 0에서  y,x에 대해서 방문했다는 표식을 남길 수 있는거 같아서 무한 루프에 빠질 것 같진 않은데..

cache[y][x]  += cache[y][x] += solve(next_y, next_x)

이 부분을 보면

cache[y][x]에 값이 바로 바로 누적되다보니까 

다시 y,x를 만났을 떄 항상 0을 반환하는게 아니라 현재 값이 누적되고 있는 중인 cache[y][x] 값을 반환하게 되어서

중복된 연산으로 원래보다 더 큰 답을 가질 것 같은데... 이유를 모르겠습니다.

댓글을 작성하려면 로그인해야 합니다.