반례:

그건 끝에 도달할 수 없으므로 올바르지 않은 입력입니다.

그리고 이 문제에 굳이 DP를 쓸 필요가 있나? 라는 생각이 듭니다. 

굳이 DP로 푸시고 싶으시다면 벨먼포드 같이 "F(r, c, e) = (1, 1) 에서 (r, c) 까지 e개 이하의 간선을 쓰는 최단 거리"로 정의 해서 풀 수 있겠지만.. 

시간 복잡도도 O(n^4)으로 시간초과 까지는 안나더라도 시간초과에 근접한 코드가 나올것 같습니다.

아 문제를 잘못 읽었네요 (제 첫번째 댓글은 무시해주세요)

반례가 필요하시다면 다음과 같은 것이 있습니다.

dp를 행과 열에 대해서만 수행해서는 최적해를 얻을 수 없다는 뜻입니다.

감사합니다. 조금 더 고민해볼게요😊

음.. 그런데 궁금한 점이 있는데요

@sohn0356 님 코드에서 

int nR = r + dY[i]; 

int nC = c + dX[i];

이렇게 바뀌어야 원래 질문자님께서 원하시는 의도대로 동작하는 코드아닌가요..?

행과 열을 y, x로 쓸지, x, y로 쓸지는 문제 푸는 사람 마음입니다. 어느 쪽으로 쓰든 4방향이 모두 탐색되는 건 동일합니다.

@djm03178 답변 감사합니다.

코드를 보니까 nR이 dy와 연결되어야 제대로 정확히 맵을 탐색한다고 생각해서

저렇게 수정하고 돌렸더니 8이라는 답이 올바르게 출력되어서 답변달았던거였는데..

저도 이 질문의 질문자님과 같은 방식으로 접근했는데 2차원 dp로는 최적해를 구할 수 없다는 거에 대한 반례를 알 수 있을까요?

메모이제이션을 사용한 dfs를 돌리면 현재 위치에서의 최적해가 도출되고, 이 값들의 미니멈을 구하면 구할 수 있을거라고 생각했는데.. 틀렸습니다가 나오네요

혹시 조언을 얻을 수 있을까요?

@sourish92 저도 DP로 풀어보려고 디버깅하면서 여러 번 고민해봤는데 제일 큰 문제는 DP의 탐색을 하게 되면 한 번 갔던 곳의 탐색을 다시 하게 된 다는 거였습니다. 제가 처음 짠 코드는 ↓→↑←으로 검색을 하게 되는데 DFS나 BFS랑 다르게 한 번 갔던 길이어도 갈 수만 있으면 가기 때문에 문제에서 원하는 최적해를 찾을 수 없습니다.  X랑 Y고쳤을 때 된 이유는 단순히 검색하는 우선순위가 바뀌어서일 뿐이고 본질적인 문제가 해결이 안 되었을 겁니다. 아마 예제의 y=x 대칭을 해보면 반례가 될 거 같습니다.

@sourish92 한 번 더 DP로 한 번 짜봤는데 시간초과나네여..ㅠㅠ