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

in Algorithm on 그래프 이론

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

풀이

격자로 이루어진 땅을 건너가야하는데 세칸을 이동할 때 마다 격자에 써있는 만큼의 풀을 먹어야 한다.

한칸을 이동할 때는 T만큼의 비용이 든다.

격자 칸마다 다른 가중치가 있다. 즉, 다익스트라를 이용해 문제를 풀면 된다.

3칸을 이동하는 방법은 ABA 처럼 갔던 칸에 다시 방문하는 방법이 있고, ABC처럼 다른 칸에 갈 수도 있다.

이러한 방법들을 적어보니 16가지가 된다. 이차원 배열로 만들어 사용했다.

static int[][] vector = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 }, { 3, 0 }, { -3, 0 }, { 0, 3 }, { 0, -3 },
            { 2, 1 }, { -2, 1 }, { 1, 2 }, { 1, -2 }, { 2, -1 }, { -2, -1 }, { -1, 2 }, { -1, -2 } };

dist[][] 배열을 만들어 다익스트라 알고리즘을 통해 채워나가면서

최종 목적지까지의 거리가 2이하가 되면 답을 갱신해주었다.

메모리: 23480KB

시간: 272ms

언어: Java 11

코드

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

public class Main {
    static class Node {
        int r;
        int c;

        public Node(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

    static int[][] vector = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 }, { 3, 0 }, { -3, 0 }, { 0, 3 }, { 0, -3 },
            { 2, 1 }, { -2, 1 }, { 1, 2 }, { 1, -2 }, { 2, -1 }, { -2, -1 }, { -1, 2 }, { -1, -2 } };

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int T = Integer.parseInt(st.nextToken());

        int[][] field = new int[N][N];
        int[][] dist = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                field[i][j] = Integer.parseInt(st.nextToken());
                dist[i][j] = Integer.MAX_VALUE;
            }
        }
        dist[0][0] = 0;

        int ans = Integer.MAX_VALUE;
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(0, 0));

        while (!queue.isEmpty()) {
            Node node = queue.poll();

            int remain = Math.abs(N - 1 - node.r) + Math.abs(N - 1 - node.c);
            if (remain <= 2) {
                ans = Math.min(ans, dist[node.r][node.c] + remain * T);
            }

            for (int i = 0; i < 16; i++) {
                int nr = node.r + vector[i][0];
                int nc = node.c + vector[i][1];

                if (nr < 0 || nc < 0 || nr >= N || nc >= N) {
                    continue;
                }

                if (dist[nr][nc] > dist[node.r][node.c] + field[nr][nc] + 3 * T) {
                    dist[nr][nc] = dist[node.r][node.c] + field[nr][nc] + 3 * T;
                    queue.add(new Node(nr, nc));
                }
            }
        }

        System.out.println(ans);
    }

}