[Python] 백준 14461번: 소가 길을 건너간 이유 7

https://www.acmicpc.net/problem/14461

14461번: 소가 길을 건너간 이유 7

 

 > 접근

초기에는 단순히 3차원 DP를 이용하여 다익스트라를 돌리는 식으로 문제를 풀었으나, 더 효율적인 방법이 가능하였다.

바로 3칸 이동을 기본 전제하에 다익스트라를 돌리고, 마지막 칸을 기준으로 2회 이내 도달 가능한 범위에서 결과값을 얻어오는 것이다. 굳이 이렇게 하는 것은, 원하는 최소 시간에 해당하는 루트의 이동 횟수가 무조건 3의 배수일 리가 없기 때문이다.

예제 입력 1에서 다익스트라의 결과는 위와 같다. 빨간 박스 안의 것들이 최솟값의 후보들이며, 27에서 2번 이동하여 얻어진 결과인 31이 정답이 된다.

 

# -*- coding: utf-8 -*-
import sys
import queue
input = sys.stdin.readline

# 3회 이동 시 가능한 상대 좌표
# 상하좌우 / 체스 나이트 / 3칸 상하좌우
dx = [1,-1,0,0, 2,2,-2,-2,1,-1,1,-1, 3,-3,0,0]
dy = [0,0,1,-1, 1,-1,1,-1,2,2,-2,-2, 0,0,3,-3]

def f():   
  dist = [[float('inf')]*N for _ in range(N)]
  dist[0][0] = 0
  pq = queue.PriorityQueue()
  pq.put([0, 0, 0]) # dist, x, y

  # 3칸 단위 다익스트라
  while(not pq.empty()):
    d, x, y = pq.get()
    for k in range(16):
      nx, ny = x + dx[k], y + dy[k]        

      if(0<=nx<=N-1 and 0<=ny<=N-1):        
        nd = d + 3*T + grid[nx][ny]
        if(dist[nx][ny] > nd):
          dist[nx][ny] = nd
          pq.put([nd,nx,ny])
                       
  # 마지막 칸에서 2회 이내로 도달 가능한 범위에서 최솟값을 구한다.      
  return min(
    dist[-1][-1],
    dist[-2][-1] + T, dist[-1][-2],
    dist[-3][-1] + 2*T, dist[-2][-2] + 2*T, dist[-1][-3] + 2*T
  )


if __name__ == '__main__':
  N, T = map(int, input().split())
  grid = [list(map(int, input().split())) for _ in range(N)]    
                                 
  print(f())