[platinum4] [풀이, 분류 미확인]16156 장애물 달리기

 

 

이 문제의 어려운 점은 어떻게 처음에 잘 시작해서 다익스트라를 한번만 돌려 끝낼 것이냐 이다.

 

마지막 열은 어떤 행이든 , 도착만 하면 끝나므로 마지막 열들의 점들을 (1,4) (2,4) ... 한점으로 생각해도 될 것이다.

따라서 마지막 열부터 시작해서 (1,1), (2,1) (3,1 ).... (N, 1)들에 도착할때의 최단 경로들을 카운트하면 다익스트라를 한번만 돌려도 될 것이다.

 

또한 마지막열에서 그 전열까지의 경로는 초록색 경로는 되지만, 빨간색 경로는 불가능 하다. (1,4)에서 시작하던 (3,4)에서 시작하던, 상관 없는데 굳이 (3,4) 에서 (2,4) -> (1,4) -> (1,3) 을 거쳐가며 구할 필요는 없다.

따라서 다음그림과 같이 나타낼 수 있다.

다음과같이 (2,5,8,10 ) 을 하나의 점으로 나타내고, (1,3) 사이 간선은 거리가 2, (2,3)은 5, ... 으로 나타낼 수 있을 것이다.

 

그러나 추상적으로 하나의 점으로 나타낸거지 경로를 추적할때 원래 출발점이 몇행인지 알아야 (i,M)에 몇개를 배치할 지  카운트가 가능하므로, 

pq에 (1,4)(2,4)(3,4)(4,4)를 넣고 시작한다.  또한 dp[1][4] , dp[2][4] ... dp[4][4] 는 0 으로 시작하게 되면 다익스트라 돌릴때 

(1,4) ->(2,4)  (3,4) ->(4,4) ... 와 같은 과정을 생략 할 수 있다. 

pq에 마지막열을 한꺼번에 넣고 시작하는게 중요했다. 마지막 열의 어떤 행에서 시작하던, 동등하기 때문이다.

 

이제 저렇게 돌리면서  pq 를 poll 했을 때(i , 1)이면, i 일때 방문했는지 확인하고 방문안했으면 저장해놓은 최단경로의 시작점의 행의 카운트 + 1 하면 된다.

 

pq는  { 현재 x  , 현재 y , 그동안 방문한 총합, 시작 행} 이렇게 저장하면 될 것이다.