인프런 커뮤니티 질문&답변

안녕하세요 명운님 ㅎㅎ

사실 DP로 최단거리를 푼다...

라고 봤을 때 유사한 방법 중 하나는 플로이드워셜을 들 수 있습니다.

근데 이것또한 메모이제이션을 적용한다기 보다는 완화시킬 수 있는 정점들을 다시 한번 완화를 시켜서 최단거리를 만들거든요...

그러한 완화가 이 코드에는 없기 때문에 틀리지 않았나 싶습니다.

좀 더 자세히 설명하자면요.

플루이드워셜같은 경우 모든 간선들을 다시한번 완화가 될 가능성이 있는지를 보고 더 완화를 합니다.

하지만 이 DP의 코드 경우.

예제2를 예로 들면

3 -> 7 -> 2 -> 0 -> 1 

까지의 간선을 만들면 더이상 완화를 하지 않습니다. 그다음에는 그저 메모이제이션이 일어나겠죠.

하지만 정답은

그 다음. 완화를 해야 하는

3 7 2 0 1
2 8 0 9 1
1 2 1 8 1

3, 2, 1, 2, 1, 0, 2, 0, 1, 1, 1

이후..

0 5

-> 19

이라는 간선인데요.

이게 반례가됩니다.

명운님이 만드신 DP의 점화식은 이것입니다.

dp[i][j][d] = min( i, j 이후의 4방향으로 부터의 거리)

근데 여기서 드는 의문은

dp[i][j] = min(i, j 이후의 4방향으로부터의 거리)

가 맞지 않나라는 생각과

이렇게 했을 때 이후에 만약 다시한번 어떠한 간선을 기반으로 저 정점을 완화시킬 때 정점자체가 이미 메모이제이션이 걸려있어서 완화 가 안 될 것같습니다.

예를 들어

1 -> 2 -> 3 -> 4

-> 5

에서 DP로 하게 되면 3에는 최소거리가 담겨있겠지만

예를 들어

2 -> 6 -> 7 -> 3 이라는 간선이 있고 이게 최적해라면

그 때 3정점까지 드갔을 때 이미 계산된 3이라는 값이 있기 때문에 메모이제이션으로 return ret 이 될것이고 완화가 안 될 것 같습니다.

감사합니다.