1. 문제 설명

소가 길을 건너간 이유 7

2. 문제 분석

다익스트라 알고리즘으로 움직인 횟수를 카운트하면서 풀을 먹을 때를 고를 수 있다.

• 처음에는 움직인 카운트가 3의 배수가 되면 노드 값을 추가하고, 나머지는 t를 더해주었다. 이 경우 업데이트가 똑바로 되지 않아(3의 배수가 되기 전 t를 더한 케이스가 최솟값이기 되기 때문에 똑바로 갱신이 안 되었음) 풀을 먹을 때와 나머지 경우를 어떻게 처리할지 곤란했다. 몇 십 분 동안 고민한 뒤 검색해보니, 처음부터 3의 배수처럼 풀을 먹는 것을 기준으로 다음 비용을 택할 수 있었다. 만일 현재 위치가 맨해튼 거리로 도착지와 2 이하일 때에는 최솟값을 갱신해주면 답을 구할 수 있었다. 1씩 움직일 때에도 3의 배수처럼 비용을 처리하고 있었는데, 이는 여러 번 움직일 수 있기 때문이다. 생각을 넓히자...!

3. 나의 풀이

import sys
import heapq

INF = sys.maxsize
n, t = map(int, sys.stdin.readline().rstrip().split())
nodes = []
for _ in range(n):
    line = list(map(int, sys.stdin.readline().rstrip().split()))
    nodes.append(line)

dx = [0, 0, 1, -1, 0, 1, 2, 3, 2, 1, 0, -1, -2, -3, -2, -1]
dy = [1, -1, 0, 0, 3, 2, 1, 0, -1, -2, -3, -2, -1, 0, 1, 2]
# 1칸 이동 + 3칸 이동 offset

def Dijkstra():
    distances = [[INF for _ in range(n)] for _ in range(n)]
    distances[0][0] = 0
    pq = []
    heapq.heappush(pq, [0, 0, 0, 0])
    answer = INF
    while pq:
        cur_cost, cur_row, cur_col, cur_cnt = heapq.heappop(pq)

        if distances[cur_row][cur_col] < cur_cost: continue

        up_to_n = abs(n-1-cur_row) + abs(n-1-cur_col)
        if up_to_n <= 2:
            answer = min(answer, cur_cost + up_to_n*t)
            # 3칸 뛰지 않아도(즉 풀을 먹지 않아도) 될 때 최솟값 갱신

        for x, y in zip(dx, dy):
            next_row, next_col = cur_row + y, cur_col + x
            if next_row < 0 or next_col < 0 or next_row >= n or next_col >= n: continue
            next_cost = 3*t + nodes[next_row][next_col]
            # 풀을 먹을 때 거리

            if distances[next_row][next_col] > next_cost + cur_cost:
                distances[next_row][next_col] = next_cost + cur_cost
                heapq.heappush(pq, [next_cost + cur_cost, next_row, next_col, cur_cnt + 1])
    return answer

ans = Dijkstra()
print(ans)