DP로 최단거리를 못구하는이유는 무한루프에 걸리기 때문이라고 알고있습니다. 오른쪽과아래로만 이동이 가능하다면

무한루프에 걸리지않지만 상하좌우가 다 움직인다면 무한루프에 걸리고 이를 방지하려면 캐시에 방문한 상태를 넣어줘야 하겠죠

그래도 제가 아는 DP로 최단 거리구하는 방법은 2가지가 있는데,

첫째는 비트마스크로 방문한 지점을 캐시에 넣어주는 방법이 있습니다.

하지만 일반적으로 2^(N*M)만큼의 공간복잡도를 필요로하므로 N*M이 굉장히 작을때에만 사용할 수 있습니다.

둘째는 map으로 메모이제이션을 하는 방법입니다.

2차원 좌표의 상태가

0100

0010

1100 이라면,

string s="010000101100" 으로 두고 map<string,int> 로 메모이제이션이 가능해집니다.

하지만 이 방법은 시간복잡도가 굉장히 커져서 왠만한 N*M크기로 사용하면 시간초과가 난다고 알고있습니다.

이 외에도 다른방법이 있다면 저도 꼭 알고싶네요..!

흠... 제가 오늘 사실 어떤 기업 코딩 테스트를 봤는데, 전형적인 BFS 문제가 나왔었습니다.

그래서 막힘없이 풀고 제출하였는데, 일반적인 테스트 케이스들은 다 맞았으나,

시간초과를 체크하는 테스트 케이스에서 전부 다 시간 초과가 뜨길래

혹시나 해서 BFS보다 빠르게 dp로도 풀 수 있었는지 궁금해서 질문해보았었습니다.

행과 열의 최대 크기는 500 밖에 되지 않았었는데... ㅠㅠ

여하튼 댓글 감사합니다.

결국은 비트마스크, 메모이제이션도 행과 열이 매우 작을 때만에 적용이 가능하다는 뜻이군요..

이런 식으로 메모이 하시면 가능할까요? 단, 여기서 dist는 최단 거리를 의미합니다.

dp[dist][...][...] = ??

floyd도 있기는 합니다만 이건 O(V^3)이였던 듯 싶고요.. 저는 가중치가 모두 같은, 그래프에서의 최단 거리를 구한다. 라는 문제가 나오면

BFS로 많이 접근합니다..

@chogahui05님께서 올려주신 것을

조금 생각해보니

어떤 점 (sy, sx)에서 어떤 점 (ey, ex)로 가는 과정(길)에서

(my, mx)도 (ey, ex)로 도달할수있다고 한다면

(sy, sx)에서 (my, mx)로 이동한 거리에

arr[my][mx] = (my, mx)에서 (ey, ex) 도달하는 최단(최소 거리)

를 더하면 되겠군요 ㅠㅠ

굳이 끝까지 BFS를 진행하지 않아도 됐었네요...

두 분 댓글 정말 감사합니다.

ps. dp로 bfs를 대체할 수 있는지는 여전히 의문이긴 합니다.

시간이 많이 지났지만 댓글 달아봅니다.

bfs로 최단경로를 구한다면 메모이제이션을 이용할 필요가 없지않나요?

Bfs로 목표지점을 포착한 순간 빠져나오면 그게 최소경로니까요

최적화를 위해선 메모이제이션을 이용하기보다 길찾기 알고리즘을 이용한 A*알고리즘을 이용하는게 더 알맞을거 같아요 :)