백준 호석사우루스(22255)

호석사우루스

1. 힌트

1) 호석사우루스가 이동하는 방법이 복잡하지만, 정점을 (호석사우루스의 위치, 몇 번째 이동을 해야하는지)로 정의하면 최소 충격량은 간선의 가중치라고 생각할 수 있습니다. 당연히 가중치가 있는 그래프에서 최단 거리는 다익스트라가 일반적입니다.

2) $3K, 3K + 1, 3K + 2$번째 이동을 반복하므로 위에서 정의한 정점에서 $2$번째 인자를 몇 번째 이동을 해야하는지를 $3$으로 나눈 나머지만 알아도 됩니다. 이렇게 하면 정점의 크기를 $N \times M \times 3$으로 줄일 수 있습니다.

2. 접근

접근보다는 구현하는 것이 까다로운 문제로 자세한 설명은 주석을 참고해주세요.

3. 구현

public class Main {
    static int N, M;
    static int[][] S;

    // 상수와 코드를 분리하면 쉽게 구현할 수 있습니다.
    // dy[t] = t번째 이동에서 갈 수 있는 방향의 y성분
    static int[][] dy = {
        { -1, 1, 0, 0 },
        { -1, 1 },
        { 0, 0 }
    };
    
    // dx[t] = t번째 이동에서 갈 수 있는 방향의 x성분
    static int[][] dx = {
        { 0, 0, -1, 1 },
        { 0, 0 },
        { -1, 1 }
    };

    static boolean inRange(int y, int x) { return 0 <= y && y < N && 0 <= x && x < M; }

    static final int INF = 987654321;

    // (y1, x1) -> (y2, x2)까지의 최단 거리
    // 도달할 수 없다면 -1 반환
    static int dijkstra(int y1, int x1, int y2, int x2) {
        PriorityQueue<Pair> pq = new PriorityQueue<>();
        pq.offer(new Pair(y1, x1, 1, 0));
        int[][][] dist = new int[N][M][3];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                Arrays.fill(dist[i][j], INF);
        // 시작 지점은 충격량이 0임
        dist[y1][x1][1] = 0;
        while (!pq.isEmpty()) {
            Pair p = pq.poll();
            int y = p.y; int x = p.x; int t = p.t; int c = p.cost;
            if (dist[y][x][t] < c) continue;
            for (int d = 0; d < dy[t].length; d++) {
                int ny = y + dy[t][d]; int nx = x + dx[t][d];
                if (!inRange(ny, nx) || S[ny][nx] == -1) continue;
                int nt = (t + 1) % 3; int nc = c + S[ny][nx];
                if (dist[ny][nx][nt] > nc) {
                    dist[ny][nx][nt] = nc;
                    pq.offer(new Pair(ny, nx, nt, nc));
                }
            }
        }
        int min = INF;
        // 몇 번째 이동으로 도착하건 상관 없이 가장 최소의 충격랑을 구해준다.
        for (int t = 0; t < 3; t++) min = Math.min(min, dist[y2][x2][t]);
        return min == INF ? -1 : min;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        S = new int[N][M];
        st = new StringTokenizer(br.readLine(), " ");
        int y1 = Integer.parseInt(st.nextToken()) - 1;
        int x1 = Integer.parseInt(st.nextToken()) - 1;
        int y2 = Integer.parseInt(st.nextToken()) - 1;
        int x2 = Integer.parseInt(st.nextToken()) - 1;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < M; j++) S[i][j] = Integer.parseInt(st.nextToken());
        }
        System.out.println(dijkstra(y1, x1, y2, x2));
    }

}
class Pair implements Comparable<Pair> {
    int y, x, t, cost;

    Pair (int y, int x, int t, int cost) { 
        this.y = y; this.x = x; this.t = t; this.cost = cost;
    }

    @Override
    public int compareTo(Pair o) { return cost - o.cost; }
}