코드는 단순해서 아마 다 이해 되실거예요 ㅠㅠ

그리고 코드 중 어디에서 오답이 발생하는지도 일단은 확인이 되어

코드에 표시해놨습니다.

처음에는 일반적인 맵 탐색 재귀 알고리즘 +  if(k>0) 이면 말점프 시도를 더 했습니다.

여기서 메모이제이션을 안 하면 답이 잘 맞아요. 그런데 엄청 느리죠.

그래서 그 다음에는 가면서 발걸음수를 +1 해가며 메모하는 방법을 사용하였어요.

나중에 이미 탐색했던 곳을 또 오게 되었을 때, 그곳에 저장된 발걸음이 제 발걸음 수보다

적거나 같으면 ( if(dp[x][y][k] <= counter ) 그냥 종료, 그렇지 않으면 다시 가보기.

그렇게 했더니 속도가 많이 빨라지긴 했지만, 그래도 재수가 없으면 

1. 최악의 경로

2. 한 발짝 빠른 재방문

3. 한 발짝 더 빠른 재재방문

....

하는 식으로 같은 길을 여러번 가는 경우가 발생하여 채점 40~50 % 쯤에서

결국 시간초과에 걸리네요. 그래서 반대로 도착했다가 돌아오면서 한 칸씩 쓰기로 했어요.

즉 도착지점에 도착하는 경우 0을 반환하고 +1씩 하며 돌아오면

각 칸마다 "여기서부터 목표지점까지의 거리"와 그 순간의 k 정보가 저장이 되어,

다른 경로를 통해 똑같은 k를 갖고 해당지점에 다시 도착했을 때는 이미 탐색을 통해 저장된

'여기서부터 골까지의 거리'를 바로 받아 뒤돌아서 1씩 더하면서 방금 왔던 경로로 그냥 돌아가는...

그러다보면 결국 최종적으로 출발점에는 출발점으로부터 목표까지의 최소거리가 저장이 되지 않을까

했는데 답이 틀리네요. 

모든 재귀호출마다 모든 경우를 시도하고, 모든 시도에 대하여 min 함수를 통해 

최솟값을 구하여 k에 따라 따로 저장하기 때문에, 생각으로는 재방문 한 곳에 이미 저장된 값을 믿고 써도 될 것 같은데...