소가 길을 건너간 이유7 (백준14461)

내가 생각한 풀이인데 예제는 통과하지만 시간 초과가 난다. 그래서 다른 사람의 풀이를 보고 풀어보았다. 

import sys 
from heapq import heapify, heappop, heappush 
input = sys.stdin.readline 
n,t = map(int, input().split())
inf = int(1e9)

dx = [1,-1,0,0] 
dy = [0,0,1,-1]
dist = [[inf for i in range(n)]for j in range(n)]
# print(dist)
gra = [list(map(int ,input().split())) for i in range(n)]

def find(a,b) :
    q = []
    # cnt = 0 
    # cost = 0 
    q.append((0,0,a,b))
    heapify(q)
    dist[a][b] = 0 
    while q :
        cost,cnt ,x,y=heappop(q)
        if dist[x][y] <cost :
            continue 
        cnt += 1 
        flag = 0 
        if cnt %3==0  :
            flag = 1 
        if x == n-1 and y==n-1 :
            return 0 
            
        for i in range(4):
            
            nx, ny = x+dx[i] , y+dy[i]
            if(0<= nx <n and 0<=ny< n):
                
                nextcost=( (cost+ gra[nx][ny]+t)if flag else (cost+t))
                if dist[nx][ny] >nextcost :
                    
                    dist[nx][ny] = nextcost 
                heappush(q, ( nextcost,cnt, nx,ny))
                
                
               
                
                
        
    
find(0,0)
print(dist[n-1][n-1])

3번 이동 시 위치할 수 있는 좌표를 찾아서 경로 탐색을 완료한다. 이후, 마지막 칸에서 가까운 위치에서 다시 최솟값을 계산한다. 

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())