문제 이해

호석사우루스는 융통성 없이 정해진 규칙을 활용해 움직인다.
규칙은 아래와 같다.

1. 3K번째는 상, 하, 좌, 우 중 한 곳으로 이동한다.
2. 3K+1번째는 상, 하 중 한 곳으로 이동한다
3. 3K+2번째는 좌, 우 중 한 곳으로 이동한다.
4. 이동하려는 곳에 벽이 있으면 이동할 수 없다.
5. 첫번째로 이동하는 것은 1(3K+1)번째 이동이다

이 때 미궁의 각 칸마다 충격량이 주어질 것이며, 호석사우르스는 해당 칸에 들어가게 되면 충격량을 받게 된다.
호석사우르스가 받는 충격량의 총량을 최소한으로 하는 방법을 찾아 최소 충격량을 구하는 문제이다.

---

문제 풀이

문제가 행렬이며, A -> B지점까지 가는 경로를 찾는 문제이다.
여기에서 우리는 "최소 경로"로 A -> B 지점까지 가고 싶다. 즉, 다익스트라 알고리즘을 활용하여 문제를 풀면 될 것이다.
우선순위 큐를 활용하여 데미지를 기준 오름차순정렬하여 큐에 저장된 최소 데미지를 가진 공간을 뽑아 활용하는 식으로 문제를 풀었다.

하지만 여기서 문제가 존재한다.
원래 Dijkstra 그래프는 갈 수 있는 방향이 모든 time step에서 동일하다. 하지만, 이 문제는 그렇지 않다.
(3K, 3K+1, 3K+2마다 이동하는 방식이 다름)

즉, "이전 Step"과 "이전에 어떻게 이동하였는가"가 중요한 문제임을 알 수 있다.
그리고, "이전 Step"에서 수행했는가 여부와 "이전 Step 계산의 중복을 막는 알고리즘"을 생각한 결과 DP를 활용하여 해결하면 된다고 생각했다.

즉, dp[x][y][1]은 (x,y)에서 3K+1번째의 이동을 시도하는 Case, dp[x][y][2]는 (x,y)에서 3K+2번째 이동을 시도하는 Case, dp[x][y][0]은 (x,y)에서 3K+0번째 이동을 시도하는 Case로 지정하여 DP를 활용하였다.

---

코드

import java.io.*;
import java.util.*;

class Point implements Comparable<Point>{
	int x;
	int y;
	int count;
	int damage;
	
	public Point(int x, int y, int count, int damage) {
		this.x = x;
		this.y = y;
		this.count = count;
		this.damage = damage;
	}
	
	@Override
	public int compareTo(Point p) {
		return this.damage - p.damage;
	}
}

public class Main {
	static StringBuilder sb = new StringBuilder();
	static FastReader sc = new FastReader();
	
	static int N, M;
	static int[][] arr;
	static int[][][] damages;
	static int start_x, start_y, end_x, end_y;
	
	static void dijkstra() {
		PriorityQueue<Point> queue = new PriorityQueue<>();
        // 우선순위 큐. damage(누적 충격량)을 기준으로 오름차순 정렬
		
		queue.add(new Point(start_x, start_y, 1, 0));
		
		while(!queue.isEmpty()) {
			Point tmp = queue.poll();
			if(tmp.x <0 || tmp.y <0 || tmp.x>=N || tmp.y>=M) continue;
			
			if(arr[tmp.x][tmp.y]==-1) continue;
            // 벽이므로 이동 못함
			
			tmp.damage = tmp.damage + arr[tmp.x][tmp.y];
			
			int re = tmp.count%3;
			
			if(damages[tmp.x][tmp.y][re] <= tmp.damage) continue;
			
			damages[tmp.x][tmp.y][re] = tmp.damage;
            // 원래 저장되어 있는 값보다 누적 충격량이 작으므로 Update
			
			if(tmp.x==end_x && tmp.y==end_y) {
            // 우선순위 큐이므로 이 조건에 다다랐을 때가 최소 충격량
				System.out.println(tmp.damage);
				return;
			}
			
			switch(tmp.count%3) {
			case 0:
            // 현재 3K번째 이동
            // 즉, 상하좌우 중 한 곳으로 이동할 수 있다.
				queue.add(
                      new Point(tmp.x+1, tmp.y, tmp.count+1, tmp.damage)
                );
				queue.add(
                      new Point(tmp.x, tmp.y+1, tmp.count+1, tmp.damage)
                );
				queue.add(
                      new Point(tmp.x-1, tmp.y, tmp.count+1, tmp.damage)
                );
				queue.add(
                      new Point(tmp.x, tmp.y-1, tmp.count+1, tmp.damage)
                );
				break;
			case 1:
            // 현재 3K+1번째 이동
            // 즉, 상하 중 한 곳으로 이동할 수 있다.
				queue.add(
                      new Point(tmp.x+1, tmp.y, tmp.count+1, tmp.damage)
                );
				queue.add(
                      new Point(tmp.x-1, tmp.y, tmp.count+1, tmp.damage)
                );
				break;
			case 2:
            // 현재 3K+2번째 이동
            // 즉, 좌우 중 한 곳으로 이동할 수 있다.
				queue.add(
                      new Point(tmp.x, tmp.y+1, tmp.count+1, tmp.damage)
                );
				queue.add(
                      new Point(tmp.x, tmp.y-1, tmp.count+1, tmp.damage)
                );
				break;
			}
		}
		
        // 여기까지 왔다는 것은 queue가 빌 때까지 도착지점까지 도달하지 못했다는
        // 것이다. 즉 답이 없는 경우이므로 -1을 출력한다.
		System.out.println(-1);
		return;
	}
	
	public static void main(String[] args) {
		
		N = sc.nextInt();
		M = sc.nextInt();
		
		arr = new int[N][M];
		damages = new int[N][M][3];
		
		start_x = sc.nextInt()-1;
		start_y = sc.nextInt()-1;
		
		end_x = sc.nextInt()-1;
		end_y = sc.nextInt()-1;
		
		for(int i =0;i<N;i++) {
			for(int j=0;j<M;j++) {
				arr[i][j] = sc.nextInt();
				damages[i][j][0] = Integer.MAX_VALUE;
				damages[i][j][1] = Integer.MAX_VALUE;
				damages[i][j][2] = Integer.MAX_VALUE;
			}
		}
        
		dijkstra();
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과