-
다익스트라와 메모이제이션아무것도 안 하는 abra/짧은 메모 2021. 9. 20. 11:12
https://www.acmicpc.net/problem/11953
11953번: 쇼핑
첫 번째 줄에는 도시의 행과 열을 나타내는 정수 H, W가 공백으로 구분되어 입력된다. (3 ≦ H ≦ 1000, 3 ≦ W ≦ 1000) 다음 줄부터 H줄에 걸쳐서 W개로 이루어진 문자열이 입력된다. 이 값들은 상점
www.acmicpc.net
처음에 격자를 그래프로 바꿔서 다익스트라를 돌리는 상상을 했었다. 물론 근처 4점의 쇼핑 상태 정보를 들고 다니는 형태로.
그런데 그러면 시간복잡도가 너무 아슬아슬해보인다. H*W*2^4에 로그가 붙으니까 시간제한이 2초라 고민되긴 하지만 좀 더 좋은 방법이 있을것 같았다.
그런데 사실 다익스트라가 필요없었다. 다익스트라 방법처럼 주변점 상태도 고려하면서 메모이제이션을 돌려주면 pq를 쓸 필요가 없어져서 log가 사라진다. 메모이제이션으로 해결할 수 있는 이유는 격자상에서 최단경로로, 즉 오른쪽 아니면 아래쪽으로만 이동하기 때문에 그래프에 위상이 존재하게 되기 때문인것 같다.
결론: DAG에서 다익스트라를 돌리지 않도록 조심하자.
'아무것도 안 하는 abra > 짧은 메모' 카테고리의 다른 글
다익스트라 문제를 푸는 두가지 방법? (0) 2022.01.22