8-U 다른풀이 질문

Question

안녕하세요 큰돌 선생님 강의 감사합니다.. 해당 문제를 처음에 보고 dp로 풀 수 있을것 같아서 접근했는데 원하는 답이 나오지 않아 선생님 강의를 보고 다익스트라로 해결하였습니다. 근데 혹시 이 문제 dp로는 해결할 수 없을까요? http://boj.kr/b2b9e324cd1644e7a5edb8caf23830aa 처음 dp로 해결하려던 코드입니다. 사실 예제 2번 부터 답이 틀려서 완전 틀린 코드이지만 어디가 틀렸는지 잘 모르겠습니다. dp의 매개변수로는 y좌표, x좌표, 그리고 d라는 이전에 왔던 방향을 뜻하는 매개변수를 넣었습니다. 현재의 값이 상하좌우 어디에서 온건지에 따라 최적의 값이 달라지기에 d를 추가하였습니다. dp배열의 초기값은 -1로 초기화했고, 또한 방문여부를 해결하기 위해서 visited배열을 만들어 해결하였습니다.

큰돌 · Answer

안녕하세요 명운님 ㅎㅎ 사실 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 이 될것이고 완화가 안 될 것 같습니다. 감사합니다.