다익스트라 문제를 푸는 두가지 방법?

(조금 특수하게 최단경로를 구해달라고 할 때)
1. 다익스트라를 문제에 맞게 구현
2. 문제에 맞게 그래프를 잘 변형한 뒤 전형적인 다익스트라 돌리기

1은 그냥 구현하면 되는데 문제에 따라서는 시간초과 내지는 메모리초과 뜰 수 있음
문제예시: 뱀이 된 경곽이?

2는 특정 동작과 동일한 역할을 하는 노드나 엣지를 추가함으로써 구현을 깔끔하게 하거나 시간, 메모리를 개선할 수 있지만 생각하기가 1에 비해 어려움
문제예시: boj 20987