다른 질문글에서 탐색 순서만 바꿨더니 잘 되는 건 그 순서대로 갔을 때 우연히 정답이 되는 쪽으로 탐색이 되었을 뿐입니다.

맨 처음 도착했던 그래프의 방문 상태와 두번째로 방문했을 때 방문 상태가 다를 수 있기 때문에 메모이제이션을 적용할 수 없습니다.

부분문제관의 의존성을 따져봤을 때, 사이클이 존재하는 경우에는 dp를 이용 할 수 없습니다.

이 문제는 예를 들면 (0,0)에서의 최단거리를 구하기 위해 (0,1)에서의 최단거리를 사용하고,

(0,1)에서의 최단거리를 구하기 위해서 (0,0)의 최단거리를 필요로 합니다.

코드 흐름을 따라가보면서 예시를 들어보겠습니다.

proc(0,0)의 부분문제를 반 정도 푼 상태에서, proc(0,1)을 호출합니다.

이 때 cache[0][0]에는 반 정도의 경우의 수만 고려한 최적이 아닌 답이 들어가 있습니다.

그런데 proc(0,1) 입장에서는 cache[0][0] 가 -1이 아니므로 (0,0)의 문제를 전부 푼걸로 생각해서, 이 잘못된 답을 사용하여 답을 구합니다.

그렇게 cache[0][1]에는 미완성된 답인 cache[0][0]을 이용했으므로 잘못된 답이 들어가고,

proc(0,0)이 호출했던 proc(0,1) 역시 이 잘못된 값을 리턴하여 cache[0][0]도 결국 제대로 답을 구해낼 수 없습니다.

답변 주신 모든 분들, 답변 정말 감사합니다!

@Green55 님 설명을 듣고 확실히 이해가 되었습니다.

부분문제관의 의존성을 따져봤을 때, 사이클이 존재하는 경우 DP를 이용할 수 없다는 사실을 처음 알았네요..

열심히 공부하겠습니다. 감사합니다 ㅎㅎㅎㅎㅎ

@djm03178 님 관련된 비슷한 질문글에 행과 열을 이용한 DP로는 풀 수 없다고 하셨는데..

그럼 혹시 다른 고려사항을 추가한다면 DP로도 풀 수 있는건가요?

https://www.acmicpc.net/board/... 이 댓글을 말한 것이었는데, BFS에 비해 매우 비효율적입니다.